<!DOCTYPE html>
<html lang="en-US">
  <head>
    <meta charset="utf-8" />
    <meta name="viewport" content="width=device-width,initial-scale=1" />
    <title>通过链表来思考递归 | aiyoudiao</title>
    <meta name="generator" content="VuePress 1.9.10" />
    <link rel="icon" href="/img/blog.ico">
    <script src="https://cdn.jsdelivr.net/npm/live2d-widget@3.1.4/lib/L2Dwidget.min.js"></script> <meta name="description" content="码二~">
    <meta name="keywords" content="前端博客,个人技术博客,前端,前端开发,前端框架,web前端,前端面试题,技术文档,学习,面试,JavaScript,js,ES6,TypeScript,vue,python,css3,html5,Node,git,github,gitee,markdown">
    <meta name="theme-color" content="#11a8cd">
    <meta name="viewport" content="width=device-width, initial-scale=1.0, minimum-scale=1.0, maximum-scale=1.0, user-scalable=no"> <link rel="preload" href="/assets/css/0.styles.146197cf.css" as="style"><link rel="preload" href="/assets/js/app.bd2fbc77.js" as="script"><link rel="preload" href="/assets/js/3.72c9c947.js" as="script"><link rel="preload" href="/assets/js/138.5bcea4ef.js" as="script"><link rel="preload" href="/assets/js/42.4251ca36.js" as="script"><link rel="prefetch" href="/assets/js/1.4ed4671d.js"><link rel="prefetch" href="/assets/js/10.bd6ddb58.js"><link rel="prefetch" href="/assets/js/100.20d2348f.js"><link rel="prefetch" href="/assets/js/101.ba7b784c.js"><link rel="prefetch" href="/assets/js/102.c3e2dcae.js"><link rel="prefetch" href="/assets/js/103.0f4c50f3.js"><link rel="prefetch" href="/assets/js/104.ef47a111.js"><link rel="prefetch" href="/assets/js/105.2e00f516.js"><link rel="prefetch" href="/assets/js/106.b50e19b9.js"><link rel="prefetch" href="/assets/js/107.e125a8f6.js"><link rel="prefetch" href="/assets/js/108.770493ab.js"><link rel="prefetch" href="/assets/js/109.74766d7b.js"><link rel="prefetch" href="/assets/js/11.f786a5ee.js"><link rel="prefetch" href="/assets/js/110.0b0ee5b4.js"><link rel="prefetch" href="/assets/js/111.835b0e44.js"><link rel="prefetch" href="/assets/js/112.352fa217.js"><link rel="prefetch" href="/assets/js/113.4e908557.js"><link rel="prefetch" href="/assets/js/114.7b77996d.js"><link rel="prefetch" href="/assets/js/115.bdc61268.js"><link rel="prefetch" href="/assets/js/116.d5da9b8b.js"><link rel="prefetch" href="/assets/js/117.35ab1f9f.js"><link rel="prefetch" href="/assets/js/118.517c151d.js"><link rel="prefetch" href="/assets/js/119.f7f49ba8.js"><link rel="prefetch" href="/assets/js/12.3c729a65.js"><link rel="prefetch" href="/assets/js/120.b559598b.js"><link rel="prefetch" href="/assets/js/121.bf8a2f43.js"><link rel="prefetch" href="/assets/js/122.11a0bc97.js"><link rel="prefetch" href="/assets/js/123.2bafdde7.js"><link rel="prefetch" href="/assets/js/124.dc393688.js"><link rel="prefetch" href="/assets/js/125.ed3f389a.js"><link rel="prefetch" href="/assets/js/126.8fd9a57d.js"><link rel="prefetch" href="/assets/js/127.3bf2a1f2.js"><link rel="prefetch" href="/assets/js/128.b9c671d3.js"><link rel="prefetch" href="/assets/js/129.5d331f0d.js"><link rel="prefetch" href="/assets/js/13.7b1a1fe5.js"><link rel="prefetch" href="/assets/js/130.53e4f9c6.js"><link rel="prefetch" href="/assets/js/131.dcc47e1d.js"><link rel="prefetch" href="/assets/js/132.692dcdcd.js"><link rel="prefetch" href="/assets/js/133.e293202c.js"><link rel="prefetch" href="/assets/js/134.593dccf2.js"><link rel="prefetch" href="/assets/js/135.d76d384b.js"><link rel="prefetch" href="/assets/js/136.a519c23c.js"><link rel="prefetch" href="/assets/js/137.b1821288.js"><link rel="prefetch" href="/assets/js/139.076664b0.js"><link rel="prefetch" href="/assets/js/14.35f257b2.js"><link rel="prefetch" href="/assets/js/140.a019e655.js"><link rel="prefetch" href="/assets/js/141.1f70e1c7.js"><link rel="prefetch" href="/assets/js/142.5ed728fd.js"><link rel="prefetch" href="/assets/js/143.1c8cdc78.js"><link rel="prefetch" href="/assets/js/144.b0cb125b.js"><link rel="prefetch" href="/assets/js/145.c0209a76.js"><link rel="prefetch" href="/assets/js/146.551469f4.js"><link rel="prefetch" href="/assets/js/147.1dfd721d.js"><link rel="prefetch" href="/assets/js/148.91d07ef5.js"><link rel="prefetch" href="/assets/js/149.5b88b710.js"><link rel="prefetch" href="/assets/js/15.23bbc29a.js"><link rel="prefetch" href="/assets/js/150.8301107f.js"><link rel="prefetch" href="/assets/js/151.867da089.js"><link rel="prefetch" href="/assets/js/152.935d5046.js"><link rel="prefetch" href="/assets/js/153.f39d8435.js"><link rel="prefetch" href="/assets/js/154.6b9eb2c3.js"><link rel="prefetch" href="/assets/js/155.14283ad4.js"><link rel="prefetch" href="/assets/js/156.2d7c1a2a.js"><link rel="prefetch" href="/assets/js/157.2f28d02f.js"><link rel="prefetch" href="/assets/js/158.151221ae.js"><link rel="prefetch" href="/assets/js/159.ef6d7ffe.js"><link rel="prefetch" href="/assets/js/16.1793aef7.js"><link rel="prefetch" href="/assets/js/160.de54c4ea.js"><link rel="prefetch" href="/assets/js/161.24d4e57c.js"><link rel="prefetch" href="/assets/js/162.632032fe.js"><link rel="prefetch" href="/assets/js/163.fd01cd99.js"><link rel="prefetch" href="/assets/js/164.45f203f5.js"><link rel="prefetch" href="/assets/js/165.aafe4fe1.js"><link rel="prefetch" href="/assets/js/166.1dd1d21c.js"><link rel="prefetch" href="/assets/js/167.5501b3a1.js"><link rel="prefetch" href="/assets/js/168.fbe58b1f.js"><link rel="prefetch" href="/assets/js/169.2cae7f5e.js"><link rel="prefetch" href="/assets/js/17.bbfe63f2.js"><link rel="prefetch" href="/assets/js/170.265f7c9e.js"><link rel="prefetch" href="/assets/js/171.b61f327d.js"><link rel="prefetch" href="/assets/js/172.5d0043fd.js"><link rel="prefetch" href="/assets/js/173.45284bb6.js"><link rel="prefetch" href="/assets/js/174.9130e0c4.js"><link rel="prefetch" href="/assets/js/175.2b38bddd.js"><link rel="prefetch" href="/assets/js/176.9772cf09.js"><link rel="prefetch" href="/assets/js/177.69048ebc.js"><link rel="prefetch" href="/assets/js/178.e10d7ce5.js"><link rel="prefetch" href="/assets/js/179.3789edc0.js"><link rel="prefetch" href="/assets/js/18.0807ded0.js"><link rel="prefetch" href="/assets/js/180.ab675e47.js"><link rel="prefetch" href="/assets/js/181.2e39eff0.js"><link rel="prefetch" href="/assets/js/19.becf5a76.js"><link rel="prefetch" href="/assets/js/2.eb089a4f.js"><link rel="prefetch" href="/assets/js/20.cea59652.js"><link rel="prefetch" href="/assets/js/21.58c43ff1.js"><link rel="prefetch" href="/assets/js/22.f73b825d.js"><link rel="prefetch" href="/assets/js/23.43b13730.js"><link rel="prefetch" href="/assets/js/24.f77f93ca.js"><link rel="prefetch" href="/assets/js/25.7dfaf3fb.js"><link rel="prefetch" href="/assets/js/26.629d28e5.js"><link rel="prefetch" href="/assets/js/27.4fff23ea.js"><link rel="prefetch" href="/assets/js/28.1b8ae389.js"><link rel="prefetch" href="/assets/js/29.d5cce9a0.js"><link rel="prefetch" href="/assets/js/30.961d5519.js"><link rel="prefetch" href="/assets/js/31.121dd1af.js"><link rel="prefetch" href="/assets/js/32.4a3c5df7.js"><link rel="prefetch" href="/assets/js/33.5537f44b.js"><link rel="prefetch" href="/assets/js/34.1d4d4653.js"><link rel="prefetch" href="/assets/js/35.d094209b.js"><link rel="prefetch" href="/assets/js/36.832660c5.js"><link rel="prefetch" href="/assets/js/37.145c3665.js"><link rel="prefetch" href="/assets/js/38.4f369bfe.js"><link rel="prefetch" href="/assets/js/39.ba060044.js"><link rel="prefetch" href="/assets/js/4.66d742f6.js"><link rel="prefetch" href="/assets/js/40.e50e0379.js"><link rel="prefetch" href="/assets/js/41.4ed7617c.js"><link rel="prefetch" href="/assets/js/43.d22b74c4.js"><link rel="prefetch" href="/assets/js/44.59439f9d.js"><link rel="prefetch" href="/assets/js/45.da28bc46.js"><link rel="prefetch" href="/assets/js/46.b8db1176.js"><link rel="prefetch" href="/assets/js/47.7ed16fc7.js"><link rel="prefetch" href="/assets/js/48.c982d5ed.js"><link rel="prefetch" href="/assets/js/49.a7579f55.js"><link rel="prefetch" href="/assets/js/5.08802d7d.js"><link rel="prefetch" href="/assets/js/50.103b5bf6.js"><link rel="prefetch" href="/assets/js/51.0fe9d79a.js"><link rel="prefetch" href="/assets/js/52.9ba31e26.js"><link rel="prefetch" href="/assets/js/53.0e8bc1f0.js"><link rel="prefetch" href="/assets/js/54.9566e517.js"><link rel="prefetch" href="/assets/js/55.a124abae.js"><link rel="prefetch" href="/assets/js/56.d9cf0800.js"><link rel="prefetch" href="/assets/js/57.93599da0.js"><link rel="prefetch" href="/assets/js/58.d943f85b.js"><link rel="prefetch" href="/assets/js/59.50a66488.js"><link rel="prefetch" href="/assets/js/6.a3ea60eb.js"><link rel="prefetch" href="/assets/js/60.21aa3aa3.js"><link rel="prefetch" href="/assets/js/61.6712c00f.js"><link rel="prefetch" href="/assets/js/62.eff3e4b1.js"><link rel="prefetch" href="/assets/js/63.09701d5a.js"><link rel="prefetch" href="/assets/js/64.eb440dec.js"><link rel="prefetch" href="/assets/js/65.aeed0579.js"><link rel="prefetch" href="/assets/js/66.97244c64.js"><link rel="prefetch" href="/assets/js/67.e01c5c24.js"><link rel="prefetch" href="/assets/js/68.21be91ba.js"><link rel="prefetch" href="/assets/js/69.c0849905.js"><link rel="prefetch" href="/assets/js/7.7fd40e91.js"><link rel="prefetch" href="/assets/js/70.b32bbe5d.js"><link rel="prefetch" href="/assets/js/71.0efbc0c7.js"><link rel="prefetch" href="/assets/js/72.ef963181.js"><link rel="prefetch" href="/assets/js/73.ca7dd5db.js"><link rel="prefetch" href="/assets/js/74.4483ede8.js"><link rel="prefetch" href="/assets/js/75.374ab483.js"><link rel="prefetch" href="/assets/js/76.b4a39f08.js"><link rel="prefetch" href="/assets/js/77.6b30c3cd.js"><link rel="prefetch" href="/assets/js/78.15376c33.js"><link rel="prefetch" href="/assets/js/79.3153fcec.js"><link rel="prefetch" href="/assets/js/80.9a88c684.js"><link rel="prefetch" href="/assets/js/81.1e3f842c.js"><link rel="prefetch" href="/assets/js/82.996dbd3d.js"><link rel="prefetch" href="/assets/js/83.955158bf.js"><link rel="prefetch" href="/assets/js/84.71bdc76d.js"><link rel="prefetch" href="/assets/js/85.774e49f2.js"><link rel="prefetch" href="/assets/js/86.bebf32e5.js"><link rel="prefetch" href="/assets/js/87.becdbde1.js"><link rel="prefetch" href="/assets/js/88.49e933f4.js"><link rel="prefetch" href="/assets/js/89.eeceedfd.js"><link rel="prefetch" href="/assets/js/90.3ea6dd12.js"><link rel="prefetch" href="/assets/js/91.62a6a556.js"><link rel="prefetch" href="/assets/js/92.e2ebb8f5.js"><link rel="prefetch" href="/assets/js/93.dcdefe7a.js"><link rel="prefetch" href="/assets/js/94.bf412146.js"><link rel="prefetch" href="/assets/js/95.8deadcdc.js"><link rel="prefetch" href="/assets/js/96.9977087a.js"><link rel="prefetch" href="/assets/js/97.6591f9da.js"><link rel="prefetch" href="/assets/js/98.4db7f75e.js"><link rel="prefetch" href="/assets/js/99.a61462e9.js"><link rel="prefetch" href="/assets/js/vendors~docsearch.2852b102.js"> <link rel="stylesheet" href="/assets/css/0.styles.146197cf.css">
  </head>
  <body class="theme-mode-light">
    <div id="app" data-server-rendered="true"><div class="theme-container sidebar-open have-rightmenu"><header class="navbar blur"><div title="目录" class="sidebar-button"><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" role="img" viewBox="0 0 448 512" width="50" height="50" class="icon"><path fill="currentColor" d="M436 124H12c-6.627 0-12-5.373-12-12V80c0-6.627 5.373-12 12-12h424c6.627 0 12 5.373 12 12v32c0 6.627-5.373 12-12 12zm0 160H12c-6.627 0-12-5.373-12-12v-32c0-6.627 5.373-12 12-12h424c6.627 0 12 5.373 12 12v32c0 6.627-5.373 12-12 12zm0 160H12c-6.627 0-12-5.373-12-12v-32c0-6.627 5.373-12 12-12h424c6.627 0 12 5.373 12 12v32c0 6.627-5.373 12-12 12z"></path></svg></div> <a href="/" class="home-link router-link-active"><img src="https://p3-passport.byteacctimg.com/img/user-avatar/794fdae4ff249d532da19a3c26d420ed~300x300.image" alt="aiyoudiao" class="logo"> <span class="site-name can-hide">
      aiyoudiao
    </span></a> <div class="links"><div class="sky-switch" data-v-3a03d589><label for="toggle" data-v-3a03d589><input id="toggle" type="checkbox" data-v-3a03d589><div data-v-3a03d589></div></label></div> <div class="search-box"><input aria-label="Search" autocomplete="off" spellcheck="false" value=""> <!----></div> <nav class="nav-links can-hide"><div class="nav-item"><div class="dropdown-wrapper"><button type="button" aria-label="笔记" class="dropdown-title"><!----> <span class="title" style="display:;">笔记</span> <span class="arrow right"></span></button> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/pages/84633490449/" class="nav-link">
  JavaScript
</a></li><li class="dropdown-item"><!----> <a href="/pages/2331001041/" class="nav-link">
  Vue
</a></li><li class="dropdown-item"><!----> <a href="/pages/18114480448/" class="nav-link">
  React
</a></li><li class="dropdown-item"><!----> <a href="/pages/25236260426/" class="nav-link">
  低代码
</a></li><li class="dropdown-item"><!----> <a href="/pages/35345230523/" class="nav-link">
  线性系统
</a></li><li class="dropdown-item"><!----> <a href="/pages/08313561056/" class="nav-link">
  暂未分类
</a></li></ul></div></div><div class="nav-item"><div class="dropdown-wrapper"><button type="button" aria-label="算法与设计" class="dropdown-title"><!----> <span class="title" style="display:;">算法与设计</span> <span class="arrow right"></span></button> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/pages/70741550255/" class="nav-link">
  LeetCode
</a></li><li class="dropdown-item"><!----> <a href="/pages/17845450445/" class="nav-link">
  算法
</a></li><li class="dropdown-item"><!----> <a href="/pages/90132170217/" class="nav-link">
  数据结构
</a></li><li class="dropdown-item"><!----> <a href="/pages/50546120212/" class="nav-link">
  设计模式
</a></li><li class="dropdown-item"><!----> <a href="/pages/02344550255/" class="nav-link">
  Other
</a></li></ul></div></div><div class="nav-item"><div class="dropdown-wrapper"><button type="button" aria-label="技能" class="dropdown-title"><!----> <span class="title" style="display:;">技能</span> <span class="arrow right"></span></button> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/pages/82158160216/" class="nav-link">
  PMP
</a></li><li class="dropdown-item"><!----> <a href="/pages/41858590259/" class="nav-link">
  Office
</a></li><li class="dropdown-item"><!----> <a href="/pages/02359360236/" class="nav-link">
  面试
</a></li><li class="dropdown-item"><!----> <a href="/pages/73600130213/" class="nav-link">
  Bash
</a></li></ul></div></div><div class="nav-item"><div class="dropdown-wrapper"><button type="button" aria-label="历程" class="dropdown-title"><!----> <span class="title" style="display:;">历程</span> <span class="arrow right"></span></button> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/pages/83857320232/" class="nav-link">
  流年往事
</a></li><li class="dropdown-item"><!----> <a href="/pages/93419130213/" class="nav-link">
  经验片段
</a></li><li class="dropdown-item"><!----> <a href="/pages/99744220322/" class="nav-link">
  读书杂感
</a></li></ul></div></div><div class="nav-item"><div class="dropdown-wrapper"><button type="button" aria-label="首页" class="dropdown-title"><!----> <span class="title" style="display:;">首页</span> <span class="arrow right"></span></button> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/archives/" class="nav-link">
  归档
</a></li><li class="dropdown-item"><!----> <a href="/categories/" class="nav-link">
  分类
</a></li><li class="dropdown-item"><!----> <a href="/tags/" class="nav-link">
  标签
</a></li></ul></div></div><div class="nav-item"><div class="dropdown-wrapper"><button type="button" aria-label="其它" class="dropdown-title"><!----> <span class="title" style="display:;">其它</span> <span class="arrow right"></span></button> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/pages/02657130213/" class="nav-link">
  简介
</a></li><li class="dropdown-item"><!----> <a href="/pages/5390102042/" class="nav-link">
  收藏
</a></li><li class="dropdown-item"><!----> <a href="/pages/32309510451/" class="nav-link">
  有趣
</a></li><li class="dropdown-item"><!----> <a href="/pages/23313210521/" class="nav-link">
  文档
</a></li></ul></div></div> <!----></nav></div></header> <div class="sidebar-mask"></div> <div class="sidebar-hover-trigger"></div> <aside class="sidebar" style="display:none;"><div class="blogger"><img src="/img/mar.jpg"> <div class="blogger-info"><h3>码二</h3> <span>扫微信二维码，认识一下码二吧😉。</span></div></div> <nav class="nav-links"><div class="nav-item"><div class="dropdown-wrapper"><button type="button" aria-label="笔记" class="dropdown-title"><!----> <span class="title" style="display:;">笔记</span> <span class="arrow right"></span></button> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/pages/84633490449/" class="nav-link">
  JavaScript
</a></li><li class="dropdown-item"><!----> <a href="/pages/2331001041/" class="nav-link">
  Vue
</a></li><li class="dropdown-item"><!----> <a href="/pages/18114480448/" class="nav-link">
  React
</a></li><li class="dropdown-item"><!----> <a href="/pages/25236260426/" class="nav-link">
  低代码
</a></li><li class="dropdown-item"><!----> <a href="/pages/35345230523/" class="nav-link">
  线性系统
</a></li><li class="dropdown-item"><!----> <a href="/pages/08313561056/" class="nav-link">
  暂未分类
</a></li></ul></div></div><div class="nav-item"><div class="dropdown-wrapper"><button type="button" aria-label="算法与设计" class="dropdown-title"><!----> <span class="title" style="display:;">算法与设计</span> <span class="arrow right"></span></button> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/pages/70741550255/" class="nav-link">
  LeetCode
</a></li><li class="dropdown-item"><!----> <a href="/pages/17845450445/" class="nav-link">
  算法
</a></li><li class="dropdown-item"><!----> <a href="/pages/90132170217/" class="nav-link">
  数据结构
</a></li><li class="dropdown-item"><!----> <a href="/pages/50546120212/" class="nav-link">
  设计模式
</a></li><li class="dropdown-item"><!----> <a href="/pages/02344550255/" class="nav-link">
  Other
</a></li></ul></div></div><div class="nav-item"><div class="dropdown-wrapper"><button type="button" aria-label="技能" class="dropdown-title"><!----> <span class="title" style="display:;">技能</span> <span class="arrow right"></span></button> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/pages/82158160216/" class="nav-link">
  PMP
</a></li><li class="dropdown-item"><!----> <a href="/pages/41858590259/" class="nav-link">
  Office
</a></li><li class="dropdown-item"><!----> <a href="/pages/02359360236/" class="nav-link">
  面试
</a></li><li class="dropdown-item"><!----> <a href="/pages/73600130213/" class="nav-link">
  Bash
</a></li></ul></div></div><div class="nav-item"><div class="dropdown-wrapper"><button type="button" aria-label="历程" class="dropdown-title"><!----> <span class="title" style="display:;">历程</span> <span class="arrow right"></span></button> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/pages/83857320232/" class="nav-link">
  流年往事
</a></li><li class="dropdown-item"><!----> <a href="/pages/93419130213/" class="nav-link">
  经验片段
</a></li><li class="dropdown-item"><!----> <a href="/pages/99744220322/" class="nav-link">
  读书杂感
</a></li></ul></div></div><div class="nav-item"><div class="dropdown-wrapper"><button type="button" aria-label="首页" class="dropdown-title"><!----> <span class="title" style="display:;">首页</span> <span class="arrow right"></span></button> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/archives/" class="nav-link">
  归档
</a></li><li class="dropdown-item"><!----> <a href="/categories/" class="nav-link">
  分类
</a></li><li class="dropdown-item"><!----> <a href="/tags/" class="nav-link">
  标签
</a></li></ul></div></div><div class="nav-item"><div class="dropdown-wrapper"><button type="button" aria-label="其它" class="dropdown-title"><!----> <span class="title" style="display:;">其它</span> <span class="arrow right"></span></button> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/pages/02657130213/" class="nav-link">
  简介
</a></li><li class="dropdown-item"><!----> <a href="/pages/5390102042/" class="nav-link">
  收藏
</a></li><li class="dropdown-item"><!----> <a href="/pages/32309510451/" class="nav-link">
  有趣
</a></li><li class="dropdown-item"><!----> <a href="/pages/23313210521/" class="nav-link">
  文档
</a></li></ul></div></div> <!----></nav>  <ul class="sidebar-links"><li><section class="sidebar-group collapsable depth-0"><p class="sidebar-heading"><span>LeetCode</span> <span class="arrow right"></span></p> <!----></section></li><li><section class="sidebar-group collapsable depth-0"><p class="sidebar-heading"><span>算法</span> <span class="arrow right"></span></p> <!----></section></li><li><section class="sidebar-group collapsable depth-0"><p class="sidebar-heading open"><span>数据结构</span> <span class="arrow down"></span></p> <ul class="sidebar-links sidebar-group-items"><li><a href="/pages/90132170217/" class="sidebar-link">浅聊数据结构(和算法)</a></li><li><a href="/pages/9384806026/" class="sidebar-link">封装自己的专属数组</a></li><li><a href="/pages/35925130313/" class="sidebar-link">通过封装来学习栈</a></li><li><a href="/pages/45502270327/" class="sidebar-link">通过封装来学习队列</a></li><li><a href="/pages/24249530353/" class="sidebar-link">封装自己的专属链表</a></li><li><a href="/pages/72920260326/" aria-current="page" class="active sidebar-link">通过链表来思考递归</a><ul class="sidebar-sub-headers"><li class="sidebar-sub-header"><a href="/pages/72920260326/#前言" class="sidebar-link">前言</a></li><li class="sidebar-sub-header"><a href="/pages/72920260326/#链表与递归" class="sidebar-link">链表与递归</a><ul class="sidebar-sub-headers"><li class="sidebar-sub-header"><a href="/pages/72920260326/#leectcode-203-号问题-删除链表中的元素" class="sidebar-link">leectcode 203 号问题：删除链表中的元素</a></li><li class="sidebar-sub-header"><a href="/pages/72920260326/#递归" class="sidebar-link">递归</a></li><li class="sidebar-sub-header"><a href="/pages/72920260326/#链表的天然递归结构性质-解答-leectcode-203-号问题" class="sidebar-link">链表的天然递归结构性质，解答 leectcode 203 号问题</a></li><li class="sidebar-sub-header"><a href="/pages/72920260326/#递归运行的机制及递归的-微观-解读" class="sidebar-link">递归运行的机制及递归的“微观”解读</a></li><li class="sidebar-sub-header"><a href="/pages/72920260326/#数组求和的递归解析" class="sidebar-link">数组求和的递归解析</a></li><li class="sidebar-sub-header"><a href="/pages/72920260326/#删除链表节点的递归解析" class="sidebar-link">删除链表节点的递归解析</a></li></ul></li><li class="sidebar-sub-header"><a href="/pages/72920260326/#递归算法的调试" class="sidebar-link">递归算法的调试</a><ul class="sidebar-sub-headers"><li class="sidebar-sub-header"><a href="/pages/72920260326/#代码示例" class="sidebar-link">代码示例</a></li></ul></li><li class="sidebar-sub-header"><a href="/pages/72920260326/#总结" class="sidebar-link">总结</a></li><li class="sidebar-sub-header"><a href="/pages/72920260326/#扩展" class="sidebar-link">扩展</a><ul class="sidebar-sub-headers"><li class="sidebar-sub-header"><a href="/pages/72920260326/#双链表" class="sidebar-link">双链表</a></li><li class="sidebar-sub-header"><a href="/pages/72920260326/#循环链表" class="sidebar-link">循环链表</a></li><li class="sidebar-sub-header"><a href="/pages/72920260326/#链表也是使用数组来实现" class="sidebar-link">链表也是使用数组来实现</a></li></ul></li></ul></li><li><a href="/pages/7445103033/" class="sidebar-link">封装自己的专属二分搜索树篇上</a></li><li><a href="/pages/67506300330/" class="sidebar-link">封装自己的专属二分搜索树篇下</a></li><li><a href="/pages/64940340334/" class="sidebar-link">封装自己的专属集合Set</a></li><li><a href="/pages/3284303033/" class="sidebar-link">封装自己的专属映射Map</a></li><li><a href="/pages/06634350335/" class="sidebar-link">封装自己的专属堆Heap</a></li><li><a href="/pages/23101220422/" class="sidebar-link">封装自己的优先队列PriorityQueue</a></li><li><a href="/pages/0300408048/" class="sidebar-link">封装自己的专属线段树SegmentTree</a></li></ul></section></li><li><section class="sidebar-group collapsable depth-0"><p class="sidebar-heading"><span>设计模式</span> <span class="arrow right"></span></p> <!----></section></li><li><section class="sidebar-group collapsable depth-0"><p class="sidebar-heading"><span>Other</span> <span class="arrow right"></span></p> <!----></section></li><li><section class="sidebar-group collapsable depth-0"><p class="sidebar-heading"><span>vue3设计与实现</span> <span class="arrow right"></span></p> <!----></section></li></ul> </aside> <div><main class="page"> <div class="theme-vdoing-wrapper bg-style-1"><div class="articleInfo-wrap" data-v-18fb2c02><div class="articleInfo" data-v-18fb2c02><ul class="breadcrumbs" data-v-18fb2c02><li data-v-18fb2c02><a href="/" title="首页" class="iconfont icon-home router-link-active" data-v-18fb2c02></a></li> <li data-v-18fb2c02><a href="/categories/?category=%E7%AE%97%E6%B3%95%E4%B8%8E%E8%AE%BE%E8%AE%A1" title="分类" data-v-18fb2c02>
          算法与设计
        </a></li> <li data-v-18fb2c02><a href="/categories/?category=%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84" title="分类" data-v-18fb2c02>
          数据结构
        </a></li> <!----></ul> <div class="info" data-v-18fb2c02><div title="作者" class="author iconfont icon-touxiang" data-v-18fb2c02><a href="javascript:;" data-v-18fb2c02>aiyoudiao</a></div> <div title="创建时间" class="date iconfont icon-riqi" data-v-18fb2c02><a href="javascript:;" data-v-18fb2c02>2022-03-21</a></div> <!----></div></div></div> <!----> <div class="content-wrapper"><div class="right-menu-wrapper"><div class="right-menu-margin"><div class="right-menu-content"></div></div></div> <h1><!----> <span>
            通过链表来思考递归
          </span></h1> <div class="theme-vdoing-content content__default"><h2 id="前言"><a href="#前言" class="header-anchor">#</a> 前言</h2> <p>上篇文章已经从底层完整实现了一个单链表这样的数据结构，并且也依托链表这样的数据结构实现了栈和队列，在实现队列的时候对链表进行了一些改进。<br>
递归不光用于树这样的结构中还可以用在链表这样的结构中，链表本身就天然的具有递归结构性质，只不过链表太简单了，它是一个线性结构，所以可以使用非递归的方式，如使用循环的方式就可以非常容易的解决链表的问题，从链表开始就要打好递归的基础，对深入学习树结构包括更加深刻的理解递归算法都是非常有好处的。</p> <p>还是那句老话：光看文章能够掌握两成，动手敲代码、动脑思考、画图才可以掌握八成。<a href="https://link.juejin.cn/?target=https%3A%2F%2Fgithub.com%2Faiyoudiao%2FMaoDataStructures" target="_blank" rel="noopener noreferrer">源码仓库<span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a></p> <p><strong>不要完美主义。掌握好“度”。</strong></p> <p>太过于追求完美会把自己逼的太紧，会产生各种焦虑的心态，最后甚至会怀疑自己，温故而知新，不要停止不前，掌握好这个度，不存在你把那些你认为完全掌握了，然后就成了某一个领域的专家，相反一旦你产生很浓厚的厌恶感，那么就意味着你即将会放弃或者已经选择了放弃，虽然你之前想把它做到 100 分，但是由于你的放弃让它变为 0 分。</p> <p>学习本着自己的目标去。不要在学的过程中偏离了自己的目标。要分清主次。
难的东西，你可以慢慢的回头看一看。那样才会更加的柳暗花明，更能提升自己的收获。</p> <h2 id="链表与递归"><a href="#链表与递归" class="header-anchor">#</a> 链表与递归</h2> <p>通过 leetcode 上与链表相关的问题来学习递归，在 leetcode 上提交链表相关的问题，还有一些其它需要注意的地方，与此同时在 leetcode 上解决与链表相关的问题，思路在有一些地方和之前自自定义链表是不同的，这里面的关键不同是在于有些情况下做这些程序是以节点为中心的而不会包装一个整体的链表类。</p> <h3 id="leectcode-203-号问题-删除链表中的元素"><a href="#leectcode-203-号问题-删除链表中的元素" class="header-anchor">#</a> leectcode 203 号问题：删除链表中的元素</h3> <p>先找到这个链表中这个节点之前的那个节点，但是对于头节点来说没有之前的那个节点，所以就要特殊处理或者使用虚拟头节点来统一这个操作。</p> <p>为了更好的测试，我自定义了一个将数组转换为链表的方法。<br>
方法解析：链表的第一个节点就是你创建的这个节点，这个节点的值也是数组的第一个值，其它的节点通过第一个节点的 next 进行关联，对应的值为数组中的每个值。</p> <h4 id="代码及测试用例"><a href="#代码及测试用例" class="header-anchor">#</a> 代码及测试用例</h4> <p><code>(class: ListNode, class: Solution,class: Solution2, class: Main)</code></p> <p><strong>ListNode</strong></p> <div class="language-js extra-class"><pre class="language-js"><code><span class="token keyword">class</span> <span class="token class-name">ListNode</span> <span class="token punctuation">{</span>
  <span class="token function">constructor</span><span class="token punctuation">(</span><span class="token parameter">val</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
      <span class="token keyword">this</span><span class="token punctuation">.</span>val <span class="token operator">=</span> val<span class="token punctuation">;</span>
      <span class="token keyword">this</span><span class="token punctuation">.</span>next <span class="token operator">=</span> <span class="token keyword">null</span><span class="token punctuation">;</span>
  <span class="token punctuation">}</span>

  <span class="token comment">// 将一个数组对象 转换为一个链表 并且追加到当前节点上</span>
  <span class="token function">appendToLinkedListNode</span><span class="token punctuation">(</span><span class="token parameter">array</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
      <span class="token keyword">let</span> head <span class="token operator">=</span> <span class="token keyword">null</span><span class="token punctuation">;</span>
      <span class="token keyword">if</span> <span class="token punctuation">(</span><span class="token keyword">this</span><span class="token punctuation">.</span>val <span class="token operator">===</span> <span class="token keyword">null</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token comment">// 头部添加</span>
        head <span class="token operator">=</span> <span class="token keyword">this</span><span class="token punctuation">;</span>
        head<span class="token punctuation">.</span>val <span class="token operator">=</span> array<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span><span class="token punctuation">;</span>
        head<span class="token punctuation">.</span>next <span class="token operator">=</span> <span class="token keyword">null</span><span class="token punctuation">;</span>
      <span class="token punctuation">}</span> <span class="token keyword">else</span> <span class="token punctuation">{</span>
        <span class="token comment">// 插入式</span>
        head <span class="token operator">=</span> <span class="token keyword">new</span> <span class="token class-name">ListNode</span><span class="token punctuation">(</span>array<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        head<span class="token punctuation">.</span>next <span class="token operator">=</span> <span class="token keyword">this</span><span class="token punctuation">.</span>next<span class="token punctuation">;</span>
        <span class="token keyword">this</span><span class="token punctuation">.</span>next <span class="token operator">=</span> head<span class="token punctuation">;</span>
      <span class="token punctuation">}</span>

      <span class="token comment">// 添加节点的方式  头部添加、尾部添加、中间插入</span>

      <span class="token comment">// 尾部添加节点的方式</span>
      <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">var</span> i <span class="token operator">=</span> <span class="token number">1</span><span class="token punctuation">;</span> i <span class="token operator">&lt;</span> array<span class="token punctuation">.</span>length<span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        head<span class="token punctuation">.</span>next <span class="token operator">=</span> <span class="token keyword">new</span> <span class="token class-name">ListNode</span><span class="token punctuation">(</span>array<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        head <span class="token operator">=</span> head<span class="token punctuation">.</span>next<span class="token punctuation">;</span>
      <span class="token punctuation">}</span>
  <span class="token punctuation">}</span>

  <span class="token comment">// 输出链表中的信息</span>
  <span class="token comment">// @Override toString 2018-10-21-jwl</span>
  <span class="token function">toString</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
      <span class="token keyword">let</span> arrInfo <span class="token operator">=</span> <span class="token template-string"><span class="token template-punctuation string">`</span><span class="token string">ListNode: \n</span><span class="token template-punctuation string">`</span></span><span class="token punctuation">;</span>
      arrInfo <span class="token operator">+=</span> <span class="token template-string"><span class="token template-punctuation string">`</span><span class="token string">data = front  [</span><span class="token template-punctuation string">`</span></span><span class="token punctuation">;</span>
      <span class="token keyword">let</span> node <span class="token operator">=</span> <span class="token keyword">this</span><span class="token punctuation">;</span>
      <span class="token keyword">while</span> <span class="token punctuation">(</span>node<span class="token punctuation">.</span>next <span class="token operator">!==</span> <span class="token keyword">null</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        arrInfo <span class="token operator">+=</span> <span class="token template-string"><span class="token template-punctuation string">`</span><span class="token interpolation"><span class="token interpolation-punctuation punctuation">${</span>node<span class="token punctuation">.</span>val<span class="token interpolation-punctuation punctuation">}</span></span><span class="token string">-&gt;</span><span class="token template-punctuation string">`</span></span><span class="token punctuation">;</span>
        node <span class="token operator">=</span> node<span class="token punctuation">.</span>next<span class="token punctuation">;</span>
      <span class="token punctuation">}</span>
      arrInfo <span class="token operator">+=</span> <span class="token template-string"><span class="token template-punctuation string">`</span><span class="token interpolation"><span class="token interpolation-punctuation punctuation">${</span>node<span class="token punctuation">.</span>val<span class="token interpolation-punctuation punctuation">}</span></span><span class="token string">-&gt;</span><span class="token template-punctuation string">`</span></span><span class="token punctuation">;</span>
      arrInfo <span class="token operator">+=</span> <span class="token string">'NULL] tail'</span><span class="token punctuation">;</span>

      <span class="token comment">// 在页面上展示</span>
      document<span class="token punctuation">.</span>body<span class="token punctuation">.</span>innerHTML <span class="token operator">+=</span> <span class="token template-string"><span class="token template-punctuation string">`</span><span class="token interpolation"><span class="token interpolation-punctuation punctuation">${</span>arrInfo<span class="token interpolation-punctuation punctuation">}</span></span><span class="token string">&lt;br /&gt;&lt;br /&gt; </span><span class="token template-punctuation string">`</span></span><span class="token punctuation">;</span>

      <span class="token keyword">return</span> arrInfo<span class="token punctuation">;</span>
  <span class="token punctuation">}</span>
<span class="token punctuation">}</span>
</code></pre></div><p><strong>Solution</strong></p> <div class="language-js extra-class"><pre class="language-js"><code><span class="token keyword">class</span> <span class="token class-name">Solution</span> <span class="token punctuation">{</span>
  <span class="token comment">// leetcode 203. 移除链表元素</span>
  <span class="token function">removeElements</span><span class="token punctuation">(</span><span class="token parameter">head<span class="token punctuation">,</span> val</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
      <span class="token comment">/**
      * Definition for singly-linked list.
      * function ListNode(val) {
      *     this.val = val;
      *     this.next = null;
      * }
      */</span>
      <span class="token comment">/**
      * @param {ListNode} head
      * @param {number} val
      * @return {ListNode}
      */</span>
      <span class="token keyword">var</span> <span class="token function-variable function">removeElements</span> <span class="token operator">=</span> <span class="token keyword">function</span><span class="token punctuation">(</span><span class="token parameter">head<span class="token punctuation">,</span> val</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token comment">// 对头步进行特殊处理</span>
        <span class="token keyword">while</span> <span class="token punctuation">(</span>head <span class="token operator">!==</span> <span class="token keyword">null</span> <span class="token operator">&amp;&amp;</span> head<span class="token punctuation">.</span>val <span class="token operator">===</span> val<span class="token punctuation">)</span> <span class="token punctuation">{</span>
            head <span class="token operator">=</span> head<span class="token punctuation">.</span>next<span class="token punctuation">;</span>
        <span class="token punctuation">}</span>

        <span class="token comment">// 处理后的头部如果为null 那直接返回</span>
        <span class="token keyword">if</span> <span class="token punctuation">(</span>head <span class="token operator">===</span> <span class="token keyword">null</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
            <span class="token keyword">return</span> <span class="token keyword">null</span><span class="token punctuation">;</span>
        <span class="token punctuation">}</span>

        <span class="token comment">// 因为头部已经做了特殊处理， head即不为null 并且 head.val不等于null</span>
        <span class="token comment">// 那么可以直接从 head的下一个节点开始判断。</span>
        <span class="token keyword">let</span> prev <span class="token operator">=</span> head<span class="token punctuation">;</span>
        <span class="token keyword">while</span> <span class="token punctuation">(</span>prev<span class="token punctuation">.</span>next <span class="token operator">!==</span> <span class="token keyword">null</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
            <span class="token keyword">if</span> <span class="token punctuation">(</span>prev<span class="token punctuation">.</span>next<span class="token punctuation">.</span>val <span class="token operator">===</span> val<span class="token punctuation">)</span> <span class="token punctuation">{</span>
              <span class="token keyword">let</span> delNode <span class="token operator">=</span> prev<span class="token punctuation">.</span>next<span class="token punctuation">;</span>
              prev<span class="token punctuation">.</span>next <span class="token operator">=</span> delNode<span class="token punctuation">.</span>next<span class="token punctuation">;</span>
              delNode <span class="token operator">=</span> <span class="token keyword">null</span><span class="token punctuation">;</span>
            <span class="token punctuation">}</span> <span class="token keyword">else</span> <span class="token punctuation">{</span>
              prev <span class="token operator">=</span> prev<span class="token punctuation">.</span>next<span class="token punctuation">;</span>
            <span class="token punctuation">}</span>
        <span class="token punctuation">}</span>

        <span class="token keyword">return</span> head<span class="token punctuation">;</span>
      <span class="token punctuation">}</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>
</code></pre></div><p><strong>Solution2</strong></p> <div class="language-js extra-class"><pre class="language-js"><code><span class="token keyword">class</span> <span class="token class-name">Solution</span> <span class="token punctuation">{</span>
  <span class="token comment">// leetcode 203. 移除链表元素</span>
  <span class="token function">removeElements</span><span class="token punctuation">(</span><span class="token parameter">head<span class="token punctuation">,</span> val</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
      <span class="token comment">/**
      * Definition for singly-linked list.
      * function ListNode(val) {
      *     this.val = val;
      *     this.next = null;
      * }
      */</span>
      <span class="token comment">/**
      * @param {ListNode} head
      * @param {number} val
      * @return {ListNode}
      */</span>
      <span class="token keyword">var</span> <span class="token function-variable function">removeElements</span> <span class="token operator">=</span> <span class="token keyword">function</span><span class="token punctuation">(</span><span class="token parameter">head<span class="token punctuation">,</span> val</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token keyword">if</span> <span class="token punctuation">(</span>head <span class="token operator">===</span> <span class="token keyword">null</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
            <span class="token keyword">return</span> <span class="token keyword">null</span><span class="token punctuation">;</span>
        <span class="token punctuation">}</span>

        <span class="token keyword">let</span> dummyHead <span class="token operator">=</span> <span class="token keyword">new</span> <span class="token class-name">ListNode</span><span class="token punctuation">(</span><span class="token number">0</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        dummyHead<span class="token punctuation">.</span>next <span class="token operator">=</span> head<span class="token punctuation">;</span>
        <span class="token keyword">let</span> cur <span class="token operator">=</span> dummyHead<span class="token punctuation">;</span>
        <span class="token keyword">while</span> <span class="token punctuation">(</span>cur<span class="token punctuation">.</span>next <span class="token operator">!==</span> <span class="token keyword">null</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
            <span class="token keyword">if</span> <span class="token punctuation">(</span>cur<span class="token punctuation">.</span>next<span class="token punctuation">.</span>val <span class="token operator">===</span> val<span class="token punctuation">)</span> <span class="token punctuation">{</span>
              cur<span class="token punctuation">.</span>next <span class="token operator">=</span> cur<span class="token punctuation">.</span>next<span class="token punctuation">.</span>next<span class="token punctuation">;</span>
            <span class="token punctuation">}</span> <span class="token keyword">else</span> <span class="token punctuation">{</span>
              cur <span class="token operator">=</span> cur<span class="token punctuation">.</span>next<span class="token punctuation">;</span>
            <span class="token punctuation">}</span>
        <span class="token punctuation">}</span>
        <span class="token keyword">return</span> dummyHead<span class="token punctuation">.</span>next<span class="token punctuation">;</span>
      <span class="token punctuation">}</span><span class="token punctuation">;</span>

      <span class="token keyword">return</span> <span class="token function">removeElements</span><span class="token punctuation">(</span>head<span class="token punctuation">,</span> val<span class="token punctuation">)</span><span class="token punctuation">;</span>
  <span class="token punctuation">}</span>
<span class="token punctuation">}</span>
</code></pre></div><p><strong>Main</strong></p> <div class="language-js extra-class"><pre class="language-js"><code><span class="token keyword">class</span> <span class="token class-name">Main</span> <span class="token punctuation">{</span>
  <span class="token function">constructor</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
      <span class="token keyword">this</span><span class="token punctuation">.</span><span class="token function">alterLine</span><span class="token punctuation">(</span><span class="token string">'leetcode 203. 删除指定元素的所有节点'</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
      <span class="token keyword">let</span> s <span class="token operator">=</span> <span class="token keyword">new</span> <span class="token class-name">Solution</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>

      <span class="token keyword">let</span> arr <span class="token operator">=</span> <span class="token punctuation">[</span><span class="token number">1</span><span class="token punctuation">,</span> <span class="token number">2</span><span class="token punctuation">,</span> <span class="token number">3</span><span class="token punctuation">,</span> <span class="token number">5</span><span class="token punctuation">,</span> <span class="token number">1</span><span class="token punctuation">,</span> <span class="token number">2</span><span class="token punctuation">,</span> <span class="token number">1</span><span class="token punctuation">,</span> <span class="token number">3</span><span class="token punctuation">,</span> <span class="token number">5</span><span class="token punctuation">,</span> <span class="token number">3</span><span class="token punctuation">,</span> <span class="token number">5</span><span class="token punctuation">,</span> <span class="token number">6</span><span class="token punctuation">,</span> <span class="token number">3</span><span class="token punctuation">,</span> <span class="token number">1</span><span class="token punctuation">,</span> <span class="token number">5</span><span class="token punctuation">,</span> <span class="token number">1</span><span class="token punctuation">,</span> <span class="token number">3</span><span class="token punctuation">]</span><span class="token punctuation">;</span>
      <span class="token keyword">let</span> node <span class="token operator">=</span> <span class="token keyword">new</span> <span class="token class-name">ListNode</span><span class="token punctuation">(</span><span class="token keyword">null</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
      node<span class="token punctuation">.</span><span class="token function">appendToLinkedListNode</span><span class="token punctuation">(</span>arr<span class="token punctuation">)</span><span class="token punctuation">;</span>

      console<span class="token punctuation">.</span><span class="token function">log</span><span class="token punctuation">(</span>node<span class="token punctuation">.</span><span class="token function">toString</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
      <span class="token keyword">let</span> result <span class="token operator">=</span> s<span class="token punctuation">.</span><span class="token function">removeElements</span><span class="token punctuation">(</span>node<span class="token punctuation">,</span> <span class="token number">1</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
      console<span class="token punctuation">.</span><span class="token function">log</span><span class="token punctuation">(</span>result<span class="token punctuation">.</span><span class="token function">toString</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
  <span class="token punctuation">}</span>

  <span class="token comment">// 将内容显示在页面上</span>
  <span class="token function">show</span><span class="token punctuation">(</span><span class="token parameter">content</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
      document<span class="token punctuation">.</span>body<span class="token punctuation">.</span>innerHTML <span class="token operator">+=</span> <span class="token template-string"><span class="token template-punctuation string">`</span><span class="token interpolation"><span class="token interpolation-punctuation punctuation">${</span>content<span class="token interpolation-punctuation punctuation">}</span></span><span class="token string">&lt;br /&gt;&lt;br /&gt;</span><span class="token template-punctuation string">`</span></span><span class="token punctuation">;</span>
  <span class="token punctuation">}</span>

  <span class="token comment">// 展示分割线</span>
  <span class="token function">alterLine</span><span class="token punctuation">(</span><span class="token parameter">title</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
      <span class="token keyword">let</span> line <span class="token operator">=</span> <span class="token template-string"><span class="token template-punctuation string">`</span><span class="token string">--------------------</span><span class="token interpolation"><span class="token interpolation-punctuation punctuation">${</span>title<span class="token interpolation-punctuation punctuation">}</span></span><span class="token string">----------------------</span><span class="token template-punctuation string">`</span></span><span class="token punctuation">;</span>
      console<span class="token punctuation">.</span><span class="token function">log</span><span class="token punctuation">(</span>line<span class="token punctuation">)</span><span class="token punctuation">;</span>
      document<span class="token punctuation">.</span>body<span class="token punctuation">.</span>innerHTML <span class="token operator">+=</span> <span class="token template-string"><span class="token template-punctuation string">`</span><span class="token interpolation"><span class="token interpolation-punctuation punctuation">${</span>line<span class="token interpolation-punctuation punctuation">}</span></span><span class="token string">&lt;br /&gt;&lt;br /&gt;</span><span class="token template-punctuation string">`</span></span><span class="token punctuation">;</span>
  <span class="token punctuation">}</span>
<span class="token punctuation">}</span>
window<span class="token punctuation">.</span><span class="token function-variable function">onload</span> <span class="token operator">=</span> <span class="token keyword">function</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
  <span class="token comment">// 执行主函数</span>
  <span class="token keyword">new</span> <span class="token class-name">Main</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span><span class="token punctuation">;</span>
</code></pre></div><h3 id="递归"><a href="#递归" class="header-anchor">#</a> 递归</h3> <p>递归是极其重要的一种组建逻辑的机制，尤其是在计算机的世界中对于高级的排序算法通常都需要使用递归，对于计算机科学来说熟练的掌握递归是极其重要的，甚至可以说初级水平与高级水平之间差距的关键分水岭。<br>
递归可以做分形图形的绘制，各种高级排序算法的可视化。</p> <p>递归的本质就是将原来的问题，转化为更小的同样的一个问题，也就是将问题规模逐渐缩小，小到一定程度，通常在递归中都是小到不能再小的时候就可以很容易的解决问题，这样一来整个问题就可以得到解决。</p> <h4 id="使用递归的例子"><a href="#使用递归的例子" class="header-anchor">#</a> 使用递归的例子</h4> <p>数组求和：求数组中 n 个元素的和</p> <p><code>Sum(arr[0...n-1]) = arr[0] + Sum(arr[1...n-1])</code> 第一次，<br> <code>Sum(arr[1...n-1]) = arr[1] + Sum(arr[2...n-1])</code> 第二次，<br> <code>...</code> 若干次<br> <code>Sum(arr[n-1...n-1]) = arr[n-1] + Sum(arr[])</code> 最后一次。<br>
每一次都是将同一个问题慢慢更小化从而演化成最基本的问题，最基本的问题解决了，然后根据之前的一些逻辑，从而解决原问题，就像一个大问题，如果他可以分解成无数个性质相同的小问题，然后对这些小问题以递归的形式进行处理，这样一来就容易多了。<br>
代码中<code>if (arr.length == cur) {return 0;}</code>就是解决最基本的问题，代码中<code>arr[cur] + sum(arr, cur+1);</code>就是在构建原问题的答案。<br>
代码中<code>sum(arr, cur+1);</code>就是不断的将原问题转化为更小的问题，很多个小问题的解加到一起，就构建出原问题的答案了。</p> <div class="language-js extra-class"><pre class="language-js"><code><span class="token keyword">class</span> <span class="token class-name">Calc</span> <span class="token punctuation">{</span>
  <span class="token function">constructor</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">{</span><span class="token punctuation">}</span>
  <span class="token comment">// 递归求和</span>
  <span class="token function">sum</span><span class="token punctuation">(</span><span class="token parameter">array<span class="token punctuation">,</span> cur <span class="token operator">=</span> <span class="token number">0</span></span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
      <span class="token comment">// 解决最基本的问题</span>
      <span class="token keyword">if</span> <span class="token punctuation">(</span>cur <span class="token operator">===</span> array<span class="token punctuation">.</span>length<span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token keyword">return</span> <span class="token number">0</span><span class="token punctuation">;</span>
      <span class="token punctuation">}</span>
      <span class="token comment">// 化归思想</span>
      <span class="token comment">// 将原问题分解为性质相同的小问题</span>
      <span class="token comment">// 将众多小问题的答案构建出原问题的答案</span>
      <span class="token keyword">return</span> array<span class="token punctuation">[</span>cur<span class="token punctuation">]</span> <span class="token operator">+</span> <span class="token keyword">this</span><span class="token punctuation">.</span><span class="token function">sum</span><span class="token punctuation">(</span>array<span class="token punctuation">,</span> cur <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
  <span class="token punctuation">}</span>
  <span class="token comment">// 尾递归求和</span>
  <span class="token function">tailSum</span><span class="token punctuation">(</span><span class="token parameter">array<span class="token punctuation">,</span> cur <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">,</span> result <span class="token operator">=</span> <span class="token number">0</span></span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
      <span class="token comment">// 解决最基本的问题</span>
      <span class="token keyword">if</span> <span class="token punctuation">(</span>cur <span class="token operator">===</span> array<span class="token punctuation">.</span>length<span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token keyword">return</span> result<span class="token punctuation">;</span> <span class="token comment">// 这里是上面的sum不一样，这里直接返回最终计算结果</span>
      <span class="token punctuation">}</span>
      <span class="token comment">// 化归思想 ： 将原问题分解为性质相同的小问题，使用小问题的解构建出原问题的解。</span>
      <span class="token comment">// 减少或者复用程序调用系统栈： 将运算操作一次性执行完毕，然后再执行子函数。</span>
      <span class="token keyword">return</span> <span class="token keyword">this</span><span class="token punctuation">.</span><span class="token function">tailSum</span><span class="token punctuation">(</span>array<span class="token punctuation">,</span> cur <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">,</span> result <span class="token operator">+</span> array<span class="token punctuation">[</span>cur<span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
  <span class="token punctuation">}</span>
<span class="token punctuation">}</span>
<span class="token keyword">class</span> <span class="token class-name">Main</span> <span class="token punctuation">{</span>
  <span class="token function">constructor</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
      <span class="token keyword">this</span><span class="token punctuation">.</span><span class="token function">alterLine</span><span class="token punctuation">(</span><span class="token string">'递归求和'</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
      <span class="token keyword">let</span> calc <span class="token operator">=</span> <span class="token keyword">new</span> <span class="token class-name">Calc</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
      <span class="token keyword">let</span> arr <span class="token operator">=</span> <span class="token punctuation">[</span><span class="token number">1</span><span class="token punctuation">,</span> <span class="token number">2</span><span class="token punctuation">,</span> <span class="token number">3</span><span class="token punctuation">,</span> <span class="token number">4</span><span class="token punctuation">]</span><span class="token punctuation">;</span>

      <span class="token keyword">let</span> arrInfo <span class="token operator">=</span> <span class="token template-string"><span class="token template-punctuation string">`</span><span class="token string">[</span><span class="token template-punctuation string">`</span></span><span class="token punctuation">;</span>
      <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">var</span> i <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> i <span class="token operator">&lt;</span> arr<span class="token punctuation">.</span>length <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        arrInfo <span class="token operator">+=</span> <span class="token template-string"><span class="token template-punctuation string">`</span><span class="token interpolation"><span class="token interpolation-punctuation punctuation">${</span>arr<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token interpolation-punctuation punctuation">}</span></span><span class="token string">,</span><span class="token template-punctuation string">`</span></span><span class="token punctuation">;</span>
      <span class="token punctuation">}</span>
      arrInfo <span class="token operator">+=</span> <span class="token template-string"><span class="token template-punctuation string">`</span><span class="token interpolation"><span class="token interpolation-punctuation punctuation">${</span>arr<span class="token punctuation">[</span>arr<span class="token punctuation">.</span>length <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">]</span><span class="token interpolation-punctuation punctuation">}</span></span><span class="token template-punctuation string">`</span></span><span class="token punctuation">;</span>
      arrInfo <span class="token operator">+=</span> <span class="token template-string"><span class="token template-punctuation string">`</span><span class="token string">]</span><span class="token template-punctuation string">`</span></span><span class="token punctuation">;</span>
      document<span class="token punctuation">.</span>body<span class="token punctuation">.</span>innerHTML <span class="token operator">+=</span> <span class="token template-string"><span class="token template-punctuation string">`</span><span class="token interpolation"><span class="token interpolation-punctuation punctuation">${</span>arrInfo<span class="token interpolation-punctuation punctuation">}</span></span><span class="token string">&lt;br /&gt;&lt;br /&gt;</span><span class="token template-punctuation string">`</span></span><span class="token punctuation">;</span>
      <span class="token keyword">this</span><span class="token punctuation">.</span><span class="token function">show</span><span class="token punctuation">(</span>calc<span class="token punctuation">.</span><span class="token function">sum</span><span class="token punctuation">(</span>arr<span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
      <span class="token keyword">this</span><span class="token punctuation">.</span><span class="token function">show</span><span class="token punctuation">(</span>calc<span class="token punctuation">.</span><span class="token function">tailSum</span><span class="token punctuation">(</span>arr<span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
  <span class="token punctuation">}</span>

  <span class="token comment">// 将内容显示在页面上</span>
  <span class="token function">show</span><span class="token punctuation">(</span><span class="token parameter">content</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
      document<span class="token punctuation">.</span>body<span class="token punctuation">.</span>innerHTML <span class="token operator">+=</span> <span class="token template-string"><span class="token template-punctuation string">`</span><span class="token interpolation"><span class="token interpolation-punctuation punctuation">${</span>content<span class="token interpolation-punctuation punctuation">}</span></span><span class="token string">&lt;br /&gt;&lt;br /&gt;</span><span class="token template-punctuation string">`</span></span><span class="token punctuation">;</span>
  <span class="token punctuation">}</span>

  <span class="token comment">// 展示分割线</span>
  <span class="token function">alterLine</span><span class="token punctuation">(</span><span class="token parameter">title</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
      <span class="token keyword">let</span> line <span class="token operator">=</span> <span class="token template-string"><span class="token template-punctuation string">`</span><span class="token string">--------------------</span><span class="token interpolation"><span class="token interpolation-punctuation punctuation">${</span>title<span class="token interpolation-punctuation punctuation">}</span></span><span class="token string">----------------------</span><span class="token template-punctuation string">`</span></span><span class="token punctuation">;</span>
      console<span class="token punctuation">.</span><span class="token function">log</span><span class="token punctuation">(</span>line<span class="token punctuation">)</span><span class="token punctuation">;</span>
      document<span class="token punctuation">.</span>body<span class="token punctuation">.</span>innerHTML <span class="token operator">+=</span> <span class="token template-string"><span class="token template-punctuation string">`</span><span class="token interpolation"><span class="token interpolation-punctuation punctuation">${</span>line<span class="token interpolation-punctuation punctuation">}</span></span><span class="token string">&lt;br /&gt;&lt;br /&gt;</span><span class="token template-punctuation string">`</span></span><span class="token punctuation">;</span>
  <span class="token punctuation">}</span>
<span class="token punctuation">}</span>
window<span class="token punctuation">.</span><span class="token function-variable function">onload</span> <span class="token operator">=</span> <span class="token keyword">function</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
  <span class="token comment">// 执行主函数</span>
  <span class="token keyword">new</span> <span class="token class-name">Main</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span><span class="token punctuation">;</span>
</code></pre></div><h4 id="小结"><a href="#小结" class="header-anchor">#</a> 小结</h4> <p>对于一个复杂的递归算法来说，这个逻辑可能是非常复杂的，虽然说转化问题是一个难点，实际上也并不是那么难，只不过很多在写逻辑的时候把自己给绕晕了，函数自己调用自己，不必过于纠结这里面程序执行的机制。</p> <p>写递归函数的时候一定要注重递归函数本身的语意，例如上面的 sum 函数，它就是用来计算一个数组从索引 cur 开始到最后一个位置之间所有的数字之和，这个就是此递归函数的<code>“宏观”语意</code>，在这样的一个语意下，在涉及转换逻辑的时候你要抛弃掉这是一个递归算法的这样的想法，递归函数本身它也是一个函数，每个函数其实就是完成一个功能。<br>
在函数 A 中调函数 B 你并不会晕，但是在函数 A 里调用函数 A，也就是在递归函数中你可能就会晕，其实这和函数 A 里调用函数 B 在本质上并没有区别。</p> <p>你可以当这是一个子逻辑，这个子逻辑里面需要传两个参数，它做的事情就是求数组里的从索引 cur 开始到最后一个位置之间所有的数字之和，你就仅仅是在用这个函数，至于或者函数是不是当前函数没必要在意，其实就是这么简单的一件事情。</p> <p>在写递归算法的时候，有些时候不需要你特别微观的陷进递归调用里的去纠结这个递归是怎么样调用的，其实你可以直接把这个递归函数当成一个子函数，这个子函数可以完成特定的功能，而你要干的事情就是利用这个子函数来构建你自己的逻辑，来解决上层的这一个问题就好了。</p> <p>注意递归函数的<code>宏观语意</code>把你要调用的递归函数当作是一个子函数或者子逻辑或者子过程，然后去想这个子过程如果去帮你解决现在的这个问题就 ok，要想熟练的掌握就需要大量的练习。</p> <h3 id="链表的天然递归结构性质-解答-leectcode-203-号问题"><a href="#链表的天然递归结构性质-解答-leectcode-203-号问题" class="header-anchor">#</a> 链表的天然递归结构性质，解答 leectcode 203 号问题</h3> <div class="language-js extra-class"><pre class="language-js"><code><span class="token keyword">class</span> <span class="token class-name">Solution</span> <span class="token punctuation">{</span>
  <span class="token comment">// leetcode 203. 移除链表元素</span>
  <span class="token function">removeElements</span><span class="token punctuation">(</span><span class="token parameter">head<span class="token punctuation">,</span> val</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
      <span class="token comment">/**
      * Definition for singly-linked list.
      * function ListNode(val) {
      *     this.val = val;
      *     this.next = null;
      * }
      */</span>
      <span class="token comment">/**
      * @param {ListNode} head
      * @param {number} val
      * @return {ListNode}
      */</span>

      <span class="token comment">// 递归求解三种方式</span>
      <span class="token keyword">var</span> <span class="token function-variable function">removeElements</span> <span class="token operator">=</span> <span class="token keyword">function</span><span class="token punctuation">(</span><span class="token parameter">head<span class="token punctuation">,</span> val</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token comment">// 解决最基本的问题</span>
        <span class="token keyword">if</span> <span class="token punctuation">(</span>head <span class="token operator">===</span> <span class="token keyword">null</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
            <span class="token keyword">return</span> <span class="token keyword">null</span><span class="token punctuation">;</span>
        <span class="token punctuation">}</span>

        <span class="token comment">// 第一种解决方式</span>
        <span class="token comment">//   let node = removeElements(head.next, val);</span>

        <span class="token comment">//   if (head.val === val) {</span>
        <span class="token comment">//     head = node;</span>
        <span class="token comment">//   } else {</span>
        <span class="token comment">//     head.next = node;</span>
        <span class="token comment">//   }</span>

        <span class="token comment">//   return head;</span>

        <span class="token comment">// 第二种解决方式</span>
        <span class="token comment">// if (head.val === val) {</span>
        <span class="token comment">//   head = removeElements(head.next, val);</span>
        <span class="token comment">// } else {</span>
        <span class="token comment">//   head.next = removeElements(head.next, val);</span>
        <span class="token comment">// }</span>
        <span class="token comment">// return head;</span>

        <span class="token comment">// 第三种方式</span>
        head<span class="token punctuation">.</span>next <span class="token operator">=</span> <span class="token function">removeElements</span><span class="token punctuation">(</span>head<span class="token punctuation">.</span>next<span class="token punctuation">,</span> val<span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token keyword">if</span> <span class="token punctuation">(</span>head<span class="token punctuation">.</span>val <span class="token operator">===</span> val<span class="token punctuation">)</span> <span class="token punctuation">{</span>
            <span class="token keyword">return</span> head<span class="token punctuation">.</span>next<span class="token punctuation">;</span>
        <span class="token punctuation">}</span> <span class="token keyword">else</span> <span class="token punctuation">{</span>
            <span class="token keyword">return</span> head<span class="token punctuation">;</span>
        <span class="token punctuation">}</span>
      <span class="token punctuation">}</span><span class="token punctuation">;</span>

      <span class="token comment">// 尾递归的方式 失败 没有到达那个程度</span>
      <span class="token comment">// var removeElements = function(head, val, node = null) {</span>
      <span class="token comment">//   if (head === null) {</span>
      <span class="token comment">//     return node;</span>
      <span class="token comment">//   }</span>

      <span class="token comment">//   return removeElements(head.next, val , node = head);</span>

      <span class="token comment">// }</span>

      <span class="token keyword">return</span> <span class="token function">removeElements</span><span class="token punctuation">(</span>head<span class="token punctuation">,</span> val<span class="token punctuation">)</span><span class="token punctuation">;</span>
  <span class="token punctuation">}</span>
<span class="token punctuation">}</span>
<span class="token keyword">class</span> <span class="token class-name">Main</span> <span class="token punctuation">{</span>
  <span class="token function">constructor</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
      <span class="token keyword">this</span><span class="token punctuation">.</span><span class="token function">alterLine</span><span class="token punctuation">(</span><span class="token string">'leetcode 203. 删除指定元素的所有节点(递归)'</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
      <span class="token keyword">let</span> s <span class="token operator">=</span> <span class="token keyword">new</span> <span class="token class-name">Solution</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>

      <span class="token keyword">let</span> arr <span class="token operator">=</span> <span class="token punctuation">[</span><span class="token number">1</span><span class="token punctuation">,</span> <span class="token number">2</span><span class="token punctuation">,</span> <span class="token number">3</span><span class="token punctuation">,</span> <span class="token number">5</span><span class="token punctuation">,</span> <span class="token number">1</span><span class="token punctuation">,</span> <span class="token number">2</span><span class="token punctuation">,</span> <span class="token number">1</span><span class="token punctuation">,</span> <span class="token number">3</span><span class="token punctuation">,</span> <span class="token number">5</span><span class="token punctuation">,</span> <span class="token number">3</span><span class="token punctuation">,</span> <span class="token number">5</span><span class="token punctuation">,</span> <span class="token number">6</span><span class="token punctuation">,</span> <span class="token number">3</span><span class="token punctuation">,</span> <span class="token number">1</span><span class="token punctuation">,</span> <span class="token number">5</span><span class="token punctuation">,</span> <span class="token number">1</span><span class="token punctuation">,</span> <span class="token number">3</span><span class="token punctuation">]</span><span class="token punctuation">;</span>
      <span class="token keyword">let</span> node <span class="token operator">=</span> <span class="token keyword">new</span> <span class="token class-name">ListNode</span><span class="token punctuation">(</span><span class="token keyword">null</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
      node<span class="token punctuation">.</span><span class="token function">appendToLinkedListNode</span><span class="token punctuation">(</span>arr<span class="token punctuation">)</span><span class="token punctuation">;</span>

      console<span class="token punctuation">.</span><span class="token function">log</span><span class="token punctuation">(</span>node<span class="token punctuation">.</span><span class="token function">toString</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
      <span class="token keyword">let</span> result <span class="token operator">=</span> s<span class="token punctuation">.</span><span class="token function">removeElements</span><span class="token punctuation">(</span>node<span class="token punctuation">,</span> <span class="token number">2</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
      console<span class="token punctuation">.</span><span class="token function">log</span><span class="token punctuation">(</span>result<span class="token punctuation">.</span><span class="token function">toString</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
  <span class="token punctuation">}</span>

  <span class="token comment">// 将内容显示在页面上</span>
  <span class="token function">show</span><span class="token punctuation">(</span><span class="token parameter">content</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
      document<span class="token punctuation">.</span>body<span class="token punctuation">.</span>innerHTML <span class="token operator">+=</span> <span class="token template-string"><span class="token template-punctuation string">`</span><span class="token interpolation"><span class="token interpolation-punctuation punctuation">${</span>content<span class="token interpolation-punctuation punctuation">}</span></span><span class="token string">&lt;br /&gt;&lt;br /&gt;</span><span class="token template-punctuation string">`</span></span><span class="token punctuation">;</span>
  <span class="token punctuation">}</span>

  <span class="token comment">// 展示分割线</span>
  <span class="token function">alterLine</span><span class="token punctuation">(</span><span class="token parameter">title</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
      <span class="token keyword">let</span> line <span class="token operator">=</span> <span class="token template-string"><span class="token template-punctuation string">`</span><span class="token string">--------------------</span><span class="token interpolation"><span class="token interpolation-punctuation punctuation">${</span>title<span class="token interpolation-punctuation punctuation">}</span></span><span class="token string">----------------------</span><span class="token template-punctuation string">`</span></span><span class="token punctuation">;</span>
      console<span class="token punctuation">.</span><span class="token function">log</span><span class="token punctuation">(</span>line<span class="token punctuation">)</span><span class="token punctuation">;</span>
      document<span class="token punctuation">.</span>body<span class="token punctuation">.</span>innerHTML <span class="token operator">+=</span> <span class="token template-string"><span class="token template-punctuation string">`</span><span class="token interpolation"><span class="token interpolation-punctuation punctuation">${</span>line<span class="token interpolation-punctuation punctuation">}</span></span><span class="token string">&lt;br /&gt;&lt;br /&gt;</span><span class="token template-punctuation string">`</span></span><span class="token punctuation">;</span>
  <span class="token punctuation">}</span>
<span class="token punctuation">}</span>
window<span class="token punctuation">.</span><span class="token function-variable function">onload</span> <span class="token operator">=</span> <span class="token keyword">function</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
  <span class="token comment">// 执行主函数</span>
  <span class="token keyword">new</span> <span class="token class-name">Main</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span><span class="token punctuation">;</span>
</code></pre></div><h3 id="递归运行的机制及递归的-微观-解读"><a href="#递归运行的机制及递归的-微观-解读" class="header-anchor">#</a> 递归运行的机制及递归的“微观”解读</h3> <p>虽然写递归函数与递归算法时要注意递归算法的宏观语意，但是站在一个更高的层面去思考这个函数它本身的功能作用是什么，也许可以帮助你更好的完成整个递归的逻辑，但是从另外一方面递归函数想，递归函数到底是怎样运转的，它内部的机制是怎样的，所以递归的运行机制也是需要了解的。</p> <p>通过数组求和与删除链表节点的递归实现来具体的观察递归的运行机制，栈的应用中说过程序调用的系统栈，子函数调用的位置会压入到一个系统栈，当子函数调用完成的时候，程序就会从系统栈中找到上次父函数调用子函数的这个位置，然后再父函数中的子函数这个位置后续继续执行，其实递归调用和子函数子过程的调用没有区别，只不过递归调用的函数还是这个函数本身而已(自己调用自己，根据某些条件终止调用自己)。</p> <p>递归的调用和子过程的调用是没有区别的，就像程序调用的系统栈一样。<br>
父函数调用子函数，子函数执行完毕之后，就会返回到上一层，也就是继续执行父函数，这个执行并不是重新执行，而是从之前那个子函数调用时的位置继续往下执行，如果子函数有返回值，那么接收一下也可以，接收完了之后继续往下执行。</p> <div class="language-js extra-class"><pre class="language-js"><code>  <span class="token constant">A0</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
  <span class="token keyword">function</span> <span class="token constant">A0</span> <span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
      <span class="token operator">...</span>
      <span class="token constant">A1</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
      <span class="token operator">...</span>
  <span class="token punctuation">}</span>
  <span class="token keyword">function</span> <span class="token constant">A1</span> <span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
      <span class="token operator">...</span>
      <span class="token constant">A2</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
      <span class="token operator">...</span>
  <span class="token punctuation">}</span>
  <span class="token keyword">function</span> <span class="token constant">A2</span> <span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
      <span class="token operator">...</span>
      <span class="token operator">...</span>
      <span class="token operator">...</span>
  <span class="token punctuation">}</span>
</code></pre></div><h4 id="递归的调用时有代价的"><a href="#递归的调用时有代价的" class="header-anchor">#</a> 递归的调用时有代价的</h4> <p>是函数调用 + 系统栈空间。比如系统栈中会记录这些函数调用的信息，如当前这个函数执行到哪儿了，当前的局部变量都是怎样的一个状态，然后给它压入系统栈。<br>
包括函数调用的本身在计算机的底层找到这个新的函数所在的位置，这些都是有一定的时间消耗的。<br>
递归调用的过程是很消耗系统栈的空间的，如果递归函数中没有处理那个最基本的情况，那么递归将一直执行下去，不会正常终止，最终终止的结果肯定就是异常报错，因为系统栈占满了，空间不足。<br>
在线性的调用过程中，当你递归的次数达到十万百万级别的话，系统占还是会被占满，因为存储了太多函数调用的状态信息。</p> <p>用递归书写逻辑其实是更简单的，这一点在线性的结构中看不出来，这是因为线性的结构非常好想，直接写循环就能解决所有的线性问题，但是一旦进入非线性的结构 如树、图，很多问题其实使用递归的方式解决将更加的简单。</p> <h3 id="数组求和的递归解析"><a href="#数组求和的递归解析" class="header-anchor">#</a> 数组求和的递归解析</h3> <h4 id="原函数"><a href="#原函数" class="header-anchor">#</a> 原函数</h4> <div class="language-js extra-class"><pre class="language-js"><code><span class="token comment">// 计算 arr[cur...n] 这个区间内的所有数字之和。</span>
<span class="token function">sum</span> <span class="token punctuation">(</span><span class="token parameter">arr<span class="token punctuation">,</span> cur <span class="token operator">=</span> <span class="token number">0</span></span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
  <span class="token comment">// 这个地方就是求解最基本问题</span>
  <span class="token comment">// 通常对于递归算法来说，</span>
  <span class="token comment">// 最基本的问题就是极其简单的，</span>
  <span class="token comment">// 基本上都是这样的一种形式</span>
  <span class="token comment">// 因为最基本的问题太过于平凡了</span>
  <span class="token comment">// 一眼就看出来那个答案是多少了</span>
  <span class="token keyword">if</span> <span class="token punctuation">(</span>arr<span class="token punctuation">.</span>length <span class="token operator">===</span> cur<span class="token punctuation">)</span> <span class="token punctuation">{</span>
      <span class="token keyword">return</span> <span class="token number">0</span><span class="token punctuation">;</span>
  <span class="token punctuation">}</span>
  <span class="token comment">// 这部分就是递归算法f最核心的部分</span>
  <span class="token comment">// 把原问题转化成更小的问题的一个过程</span>
  <span class="token comment">// 这个过程是难的，</span>
  <span class="token comment">// 这个转化为更小的问题并不简单的求一个更小的问题的答案就好了，</span>
  <span class="token comment">// 而是要根据这个更小的问题的答案构建出原问题的答案，</span>
  <span class="token comment">// 这个构建 在这里就是一个加法的过程。</span>
  <span class="token keyword">return</span> arr<span class="token punctuation">[</span>cur<span class="token punctuation">]</span> <span class="token operator">+</span> <span class="token keyword">this</span><span class="token punctuation">.</span><span class="token function">sum</span><span class="token punctuation">(</span>arr<span class="token punctuation">,</span> cur <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>
</code></pre></div><h4 id="解析原函数"><a href="#解析原函数" class="header-anchor">#</a> 解析原函数</h4> <p>递归函数的调用，本质就是就是函数调用，只不过调用的函数就是自己而已。</p> <div class="language-js extra-class"><pre class="language-js"><code><span class="token comment">// 计算 arr[cur...n] 这个区间内的所有数字之和。</span>
<span class="token function">sum</span> <span class="token punctuation">(</span><span class="token parameter">arr<span class="token punctuation">,</span> cur <span class="token operator">=</span> <span class="token number">0</span></span><span class="token punctuation">)</span> <span class="token punctuation">{</span>

      <span class="token keyword">if</span> <span class="token punctuation">(</span>arr<span class="token punctuation">.</span>length <span class="token operator">===</span> cur<span class="token punctuation">)</span> <span class="token punctuation">{</span>
            <span class="token keyword">return</span> <span class="token number">0</span><span class="token punctuation">;</span>
      <span class="token punctuation">}</span>

      temp <span class="token operator">=</span> <span class="token function">sum</span><span class="token punctuation">(</span>arr<span class="token punctuation">,</span> cur <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
      result <span class="token operator">=</span> arr<span class="token punctuation">[</span>cur<span class="token punctuation">]</span> <span class="token operator">+</span> temp<span class="token punctuation">;</span>
      <span class="token keyword">return</span> result<span class="token punctuation">;</span>
<span class="token punctuation">}</span>
</code></pre></div><p>在 sum 函数中调用到了 sum 函数，实际上是在一个新的 sum 函数中 调用逻辑，原来的 sum 函数中所有的变量保持不变，等新的 sum 函数执行完了逻辑，还会回到原来的 sum 函数中继续执行余下的逻辑。</p> <div class="language-js extra-class"><pre class="language-js"><code><span class="token comment">// 计算 arr[cur...n] 这个区间内的所有数字之和。</span>

<span class="token comment">// 代号 001</span>
<span class="token comment">// 使用 arr = [6, 10]</span>
<span class="token comment">// 调用 sum(arr, 0)</span>
<span class="token function">sum</span> <span class="token punctuation">(</span><span class="token parameter">arr<span class="token punctuation">,</span> cur <span class="token operator">=</span> <span class="token number">0</span></span><span class="token punctuation">)</span> <span class="token punctuation">{</span>

  <span class="token keyword">if</span> <span class="token punctuation">(</span>cur <span class="token operator">==</span> n<span class="token punctuation">)</span> <span class="token keyword">return</span> <span class="token number">0</span><span class="token punctuation">;</span> <span class="token comment">// n 为数组的长度：2</span>

  temp <span class="token operator">=</span> <span class="token function">sum</span><span class="token punctuation">(</span>arr<span class="token punctuation">,</span> cur <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token comment">// cur 为 0</span>
  result <span class="token operator">=</span> arr<span class="token punctuation">[</span>cur<span class="token punctuation">]</span> <span class="token operator">+</span> temp<span class="token punctuation">;</span>
  <span class="token keyword">return</span> result<span class="token punctuation">;</span>
<span class="token punctuation">}</span>

<span class="token comment">// 代号 002</span>
<span class="token comment">// 到了 上面的sum(arr, cur + 1)时</span>
<span class="token comment">// 实际 调用了 sum(arr, 1)</span>
<span class="token function">sum</span> <span class="token punctuation">(</span><span class="token parameter">arr<span class="token punctuation">,</span> cur <span class="token operator">=</span> <span class="token number">0</span></span><span class="token punctuation">)</span> <span class="token punctuation">{</span>

  <span class="token keyword">if</span> <span class="token punctuation">(</span>cur <span class="token operator">==</span> n<span class="token punctuation">)</span> <span class="token keyword">return</span> <span class="token number">0</span><span class="token punctuation">;</span> <span class="token comment">// n 为数组的长度：2</span>

  temp <span class="token operator">=</span> <span class="token function">sum</span><span class="token punctuation">(</span>arr<span class="token punctuation">,</span> cur <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token comment">// cur 为 1</span>
  result <span class="token operator">=</span> arr<span class="token punctuation">[</span>cur<span class="token punctuation">]</span> <span class="token operator">+</span> temp<span class="token punctuation">;</span>
  <span class="token keyword">return</span> result<span class="token punctuation">;</span>
<span class="token punctuation">}</span>

<span class="token comment">// 代号 003</span>
<span class="token comment">// 到了 上面的sum(arr, cur + 1)时</span>
<span class="token comment">// 实际 调用了 sum(arr, 2)</span>
<span class="token function">sum</span> <span class="token punctuation">(</span><span class="token parameter">arr<span class="token punctuation">,</span> cur <span class="token operator">=</span> <span class="token number">0</span></span><span class="token punctuation">)</span> <span class="token punctuation">{</span>

  <span class="token comment">// n 为数组的长度：2，cur 也为：2</span>
  <span class="token comment">// 所以sum函数到这里就终止了</span>
  <span class="token keyword">if</span> <span class="token punctuation">(</span>cur <span class="token operator">==</span> n<span class="token punctuation">)</span> <span class="token keyword">return</span> <span class="token number">0</span><span class="token punctuation">;</span>

  temp <span class="token operator">=</span> <span class="token function">sum</span><span class="token punctuation">(</span>arr<span class="token punctuation">,</span> cur <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token comment">// cur 为 2</span>
  result <span class="token operator">=</span> arr<span class="token punctuation">[</span>cur<span class="token punctuation">]</span> <span class="token operator">+</span> temp<span class="token punctuation">;</span>
  <span class="token keyword">return</span> result<span class="token punctuation">;</span>
<span class="token punctuation">}</span>

<span class="token comment">// 上面的代号003的sum函数执行完毕后 返回 0。</span>
<span class="token comment">//</span>
<span class="token comment">// 那么 上面的代号002的sum函数中</span>
<span class="token comment">// temp = sum(arr, cur + 1)，temp获取到的值 就为 0，</span>
<span class="token comment">// 然后继续执行代号002的sum函数里temp获取值时中断的位置 下面的逻辑，</span>
<span class="token comment">// 执行到了result = arr[cur] + temp，</span>
<span class="token comment">// temp为 0，cur 为 1，arr[1] 为 10，所以result 为 0 + 10 = 10，</span>
<span class="token comment">// 这样一来 代号002的sum函数执行完毕了，返回 10。</span>
<span class="token comment">//</span>
<span class="token comment">// 那么 代号001的sum函数中</span>
<span class="token comment">// temp = sum(arr, cur + 1)，temp获取到的值 就为 10，</span>
<span class="token comment">// 然后继续执行代号001的sum函数里temp获取值时中断的位置 下面的逻辑，</span>
<span class="token comment">// 执行到了result = arr[cur] + temp，</span>
<span class="token comment">// temp为 10，cur 为 0，arr[0] 为 6，所以result 为 6 + 10 = 16，</span>
<span class="token comment">// 这样一来 代号001的sum函数执行完毕了，返回 16。</span>
<span class="token comment">//</span>
<span class="token comment">// 代号001的sum函数没有被其它代号00x的sum函数调用，</span>
<span class="token comment">// 所以数组求和的最终结果就是 16。</span>
</code></pre></div><h4 id="调试递归函数的思路"><a href="#调试递归函数的思路" class="header-anchor">#</a> 调试递归函数的思路</h4> <p>如果对递归函数运转的机制不理解，不要对着递归函数去生看生想，在很多时候你肯定会越想越乱，不如你用一个非常小的测试数据集直接扔进这个函数中，你可以使用纸笔画或者使用 浏览器 提供的 debug功能，一步一步的去看这个程序在每一步执行后计算的结果是什么。<br>
通常使用这种方式能够帮助你更加清晰的理解程序的运转逻辑，计算机是一门工科，和工程相关的科学，工程相关的科学虽然也注重理论它背后也有理论支撑，但是从工程的角度入手来实践是非常非常重要的。<br>
很多时候你如果想理解它背后的理论，可能更好的方式不是去想这个理论，而是实际的去实践一下看看这个过程到底是怎么回事儿。</p> <h3 id="删除链表节点的递归解析"><a href="#删除链表节点的递归解析" class="header-anchor">#</a> 删除链表节点的递归解析</h3> <h4 id="原函数-2"><a href="#原函数-2" class="header-anchor">#</a> 原函数</h4> <div class="language-js extra-class"><pre class="language-js"><code><span class="token keyword">var</span> <span class="token function-variable function">removeElements</span> <span class="token operator">=</span> <span class="token keyword">function</span><span class="token punctuation">(</span><span class="token parameter">head<span class="token punctuation">,</span> val</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
  <span class="token keyword">if</span> <span class="token punctuation">(</span>head <span class="token operator">==</span> <span class="token keyword">null</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
      <span class="token keyword">return</span> <span class="token keyword">null</span><span class="token punctuation">;</span>
  <span class="token punctuation">}</span>

  head<span class="token punctuation">.</span>next <span class="token operator">=</span> <span class="token function">removeElements</span><span class="token punctuation">(</span>head<span class="token punctuation">.</span>next<span class="token punctuation">,</span> val<span class="token punctuation">)</span><span class="token punctuation">;</span>
  <span class="token keyword">if</span> <span class="token punctuation">(</span>head<span class="token punctuation">.</span>val <span class="token operator">==</span> val<span class="token punctuation">)</span> <span class="token punctuation">{</span>
      <span class="token keyword">return</span> head<span class="token punctuation">.</span>next<span class="token punctuation">;</span>
  <span class="token punctuation">}</span> <span class="token keyword">else</span> <span class="token punctuation">{</span>
      <span class="token keyword">return</span> head<span class="token punctuation">;</span>
  <span class="token punctuation">}</span>
<span class="token punctuation">}</span><span class="token punctuation">;</span>
</code></pre></div><h5 id="解析原函数-2"><a href="#解析原函数-2" class="header-anchor">#</a> 解析原函数</h5> <p>递归调用的时候就是子过程的调用，一步一步的向下调用，调用完毕之后，子过程计算出结果后再一步一步的返回给上层的调用，最终得到了最终的结果，6-&gt;7-&gt;8-&gt;null 删除掉 7 之后就是 6-&gt;8-&gt;null，节点真正的删除是发生在步骤 3 中，在使用解决了一个更小规模的问题相应的解之后，结合当前的调用，组织逻辑，组织出了当前这个问题的解，就是这样的一个过程。</p> <div class="language-js extra-class"><pre class="language-js"><code><span class="token comment">// 操作函数编号 001</span>
<span class="token keyword">var</span> <span class="token function-variable function">removeElements</span> <span class="token operator">=</span> <span class="token keyword">function</span><span class="token punctuation">(</span><span class="token parameter">head<span class="token punctuation">,</span> val</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
  <span class="token comment">// head：6-&gt;7-&gt;8-&gt;null</span>
  <span class="token comment">//步骤1</span>
  <span class="token keyword">if</span> <span class="token punctuation">(</span>head <span class="token operator">==</span> <span class="token keyword">null</span><span class="token punctuation">)</span> <span class="token keyword">return</span> <span class="token keyword">null</span><span class="token punctuation">;</span>

  <span class="token comment">//步骤2</span>
  head<span class="token punctuation">.</span>next <span class="token operator">=</span> <span class="token function">removeElements</span><span class="token punctuation">(</span>head<span class="token punctuation">.</span>next<span class="token punctuation">,</span> val<span class="token punctuation">)</span><span class="token punctuation">;</span>
  <span class="token comment">//步骤3</span>
  <span class="token keyword">return</span> head<span class="token punctuation">.</span>val <span class="token operator">==</span> val <span class="token operator">?</span> head<span class="token punctuation">.</span>next <span class="token operator">:</span> head<span class="token punctuation">;</span>
<span class="token punctuation">}</span><span class="token punctuation">;</span>
<span class="token comment">// 模拟调用，对 6-&gt;7-&gt;8-&gt;null 进行7的删除</span>
<span class="token comment">// 调用 removeElments(head, 7);</span>
<span class="token comment">// 执行步骤1，head当前的节点为6，既然不为null，所以不返回null，</span>
<span class="token comment">// 继续执行步骤2，head.next = removeElements(head.next, 7)，</span>
<span class="token comment">// 求当前节点后面的一个节点，后面的一个节点目前不知道，</span>
<span class="token comment">// 但是可以通过removeElements(head.next, 7)这样的子过程调用求出来，</span>
<span class="token comment">// 这次传入的是当前节点的next，也就是7的这个节点，7-&gt;8-&gt;null。</span>

<span class="token comment">// 操作函数编号 002</span>
<span class="token keyword">var</span> <span class="token function-variable function">removeElements</span> <span class="token operator">=</span> <span class="token keyword">function</span><span class="token punctuation">(</span><span class="token parameter">head<span class="token punctuation">,</span> val</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
  <span class="token comment">// head：7-&gt;8-&gt;null</span>
  <span class="token comment">//步骤1</span>
  <span class="token keyword">if</span> <span class="token punctuation">(</span>head <span class="token operator">==</span> <span class="token keyword">null</span><span class="token punctuation">)</span> <span class="token keyword">return</span> <span class="token keyword">null</span><span class="token punctuation">;</span>

  <span class="token comment">//步骤2</span>
  head<span class="token punctuation">.</span>next <span class="token operator">=</span> <span class="token function">removeElements</span><span class="token punctuation">(</span>head<span class="token punctuation">.</span>next<span class="token punctuation">,</span> val<span class="token punctuation">)</span><span class="token punctuation">;</span>
  <span class="token comment">//步骤3</span>
  <span class="token keyword">return</span> head<span class="token punctuation">.</span>val <span class="token operator">==</span> val <span class="token operator">?</span> head<span class="token punctuation">.</span>next <span class="token operator">:</span> head<span class="token punctuation">;</span>
<span class="token punctuation">}</span><span class="token punctuation">;</span>
<span class="token comment">// 模拟调用，对 7-&gt;8-&gt;null 进行7的删除</span>
<span class="token comment">// 调用 removeElements(head.next, 7);</span>
<span class="token comment">// head.next 会被赋值给 函数中的局部变量 head，</span>
<span class="token comment">// 也就是调用时被转换为 removeElements(head, 7);</span>
<span class="token comment">// 执行步骤1，head当前的节点为7，不为null，所以也不会返回null，</span>
<span class="token comment">// 继续执行步骤2，head.next = removeElements(head.next, 7)，</span>
<span class="token comment">// 求当前节点后面的一个节点，后面的一个节点目前不知道，</span>
<span class="token comment">// 但是可以通过removeElements(head.next, 7)这样的子过程调用求出来，</span>
<span class="token comment">// 这次传入的也是当前节点的next，也就是8的这个节点，8-&gt;null。</span>

<span class="token comment">// 操作函数编号 003</span>
<span class="token keyword">var</span> <span class="token function-variable function">removeElements</span> <span class="token operator">=</span> <span class="token keyword">function</span><span class="token punctuation">(</span><span class="token parameter">head<span class="token punctuation">,</span> val</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
  <span class="token comment">// head：8-&gt;null</span>
  <span class="token comment">// 步骤1</span>
  <span class="token keyword">if</span> <span class="token punctuation">(</span>head <span class="token operator">==</span> <span class="token keyword">null</span><span class="token punctuation">)</span> <span class="token keyword">return</span> <span class="token keyword">null</span><span class="token punctuation">;</span>

  <span class="token comment">// 步骤2</span>
  head<span class="token punctuation">.</span>next <span class="token operator">=</span> <span class="token function">removeElements</span><span class="token punctuation">(</span>head<span class="token punctuation">.</span>next<span class="token punctuation">,</span> val<span class="token punctuation">)</span><span class="token punctuation">;</span>
  <span class="token comment">// 步骤3</span>
  <span class="token keyword">return</span> head<span class="token punctuation">.</span>val <span class="token operator">==</span> val <span class="token operator">?</span> head<span class="token punctuation">.</span>next <span class="token operator">:</span> head<span class="token punctuation">;</span>
<span class="token punctuation">}</span><span class="token punctuation">;</span>
<span class="token comment">// 模拟调用，对 8-&gt;null 进行7的删除</span>
<span class="token comment">// 调用 removeElements(head.next, 7);</span>
<span class="token comment">// head.next 会被赋值给 函数中的局部变量 head，</span>
<span class="token comment">// 也就是调用时被转换为 removeElements(head, 7);</span>
<span class="token comment">// 执行步骤1，head当前的节点为7，不为null，所以也不会返回null，</span>
<span class="token comment">// 继续执行步骤2，head.next = removeElements(head.next, 7)，</span>
<span class="token comment">// 求当前节点后面的一个节点，后面的一个节点目前不知道，</span>
<span class="token comment">// 但是可以通过removeElements(head.next, 7)这样的子过程调用求出来，</span>
<span class="token comment">// 这次传入的也是当前节点的next，也就是null的这个节点，null。</span>

<span class="token comment">// 操作函数编号 004</span>
<span class="token keyword">var</span> <span class="token function-variable function">removeElements</span> <span class="token operator">=</span> <span class="token keyword">function</span><span class="token punctuation">(</span><span class="token parameter">head<span class="token punctuation">,</span> val</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
  <span class="token comment">// head：null</span>
  <span class="token comment">// 步骤1</span>
  <span class="token keyword">if</span> <span class="token punctuation">(</span>head <span class="token operator">==</span> <span class="token keyword">null</span><span class="token punctuation">)</span> <span class="token keyword">return</span> <span class="token keyword">null</span><span class="token punctuation">;</span>

  <span class="token comment">// 步骤2</span>
  head<span class="token punctuation">.</span>next <span class="token operator">=</span> <span class="token function">removeElements</span><span class="token punctuation">(</span>head<span class="token punctuation">.</span>next<span class="token punctuation">,</span> val<span class="token punctuation">)</span><span class="token punctuation">;</span>
  <span class="token comment">// 步骤3</span>
  <span class="token keyword">return</span> head<span class="token punctuation">.</span>val <span class="token operator">==</span> val <span class="token operator">?</span> head<span class="token punctuation">.</span>next <span class="token operator">:</span> head<span class="token punctuation">;</span>
<span class="token punctuation">}</span><span class="token punctuation">;</span>
<span class="token comment">// 模拟调用，对 null 进行7的删除</span>
<span class="token comment">// 调用 removeElements(head.next, 7);</span>
<span class="token comment">// head.next 会被赋值给 函数中的局部变量 head，</span>
<span class="token comment">// 也就是调用时被转换为 removeElements(head, 7);</span>
<span class="token comment">// 执行步骤1，head当前的节点为null，直接返回null，不继续向下执行了。</span>

<span class="token comment">// 操作函数编号 003</span>
<span class="token keyword">var</span> <span class="token function-variable function">removeElements</span> <span class="token operator">=</span> <span class="token keyword">function</span><span class="token punctuation">(</span><span class="token parameter">head<span class="token punctuation">,</span> val</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
  <span class="token comment">// head：8-&gt;null</span>
  <span class="token comment">//步骤1</span>
  <span class="token keyword">if</span> <span class="token punctuation">(</span>head <span class="token operator">==</span> <span class="token keyword">null</span><span class="token punctuation">)</span> <span class="token keyword">return</span> <span class="token keyword">null</span><span class="token punctuation">;</span>

  <span class="token comment">//步骤2</span>
  head<span class="token punctuation">.</span>next <span class="token operator">=</span> <span class="token function">removeElements</span><span class="token punctuation">(</span>head<span class="token punctuation">.</span>next<span class="token punctuation">,</span> val<span class="token punctuation">)</span><span class="token punctuation">;</span>
  <span class="token comment">//步骤3</span>
  <span class="token keyword">return</span> head<span class="token punctuation">.</span>val <span class="token operator">==</span> val <span class="token operator">?</span> head<span class="token punctuation">.</span>next <span class="token operator">:</span> head<span class="token punctuation">;</span>
<span class="token punctuation">}</span><span class="token punctuation">;</span>
<span class="token comment">// 这时候回到操作函数编号 004的上一层中来，</span>
<span class="token comment">// 操作函数编号 003 调用到了步骤2，并且head.next接收到的返回值为null,</span>
<span class="token comment">// 继续操作函数编号 003 的步骤3，判断当前节点的val是否为7，</span>
<span class="token comment">// 很明显函数编号003里的当前节点的val为8，所以返回当前的节点 8-&gt;null。</span>

<span class="token comment">// 操作函数编号 002</span>
<span class="token keyword">var</span> <span class="token function-variable function">removeElements</span> <span class="token operator">=</span> <span class="token keyword">function</span><span class="token punctuation">(</span><span class="token parameter">head<span class="token punctuation">,</span> val</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
  <span class="token comment">// head：7-&gt;8-&gt;null</span>
  <span class="token comment">//步骤1</span>
  <span class="token keyword">if</span> <span class="token punctuation">(</span>head <span class="token operator">==</span> <span class="token keyword">null</span><span class="token punctuation">)</span> <span class="token keyword">return</span> <span class="token keyword">null</span><span class="token punctuation">;</span>

  <span class="token comment">//步骤2</span>
  head<span class="token punctuation">.</span>next <span class="token operator">=</span> <span class="token function">removeElements</span><span class="token punctuation">(</span>head<span class="token punctuation">.</span>next<span class="token punctuation">,</span> val<span class="token punctuation">)</span><span class="token punctuation">;</span>
  <span class="token comment">//步骤3</span>
  <span class="token keyword">return</span> head<span class="token punctuation">.</span>val <span class="token operator">==</span> val <span class="token operator">?</span> head<span class="token punctuation">.</span>next <span class="token operator">:</span> head<span class="token punctuation">;</span>
<span class="token punctuation">}</span><span class="token punctuation">;</span>
<span class="token comment">// 这时候回到操作函数编号 003的上一层中来，</span>
<span class="token comment">// 操作函数编号 002 调用到了步骤2，head.next接收到的返回值为节点 8-&gt;null，</span>
<span class="token comment">// 继续操作函数编号 002 的步骤3，判断当前节点的val是否为7，</span>
<span class="token comment">// 此时函数编号 002 的当前节点的val为7，所以返回就是当前节点的next 8-&gt;null，</span>
<span class="token comment">// 也就是说不返回当前的节点 head：7-&gt;8-&gt;null ，改返回当前节点的下一个节点，</span>
<span class="token comment">// 这样一来就相当于删除了当前这个节点，改让父节点的next指向当前节点的next。</span>

<span class="token comment">// 操作函数编号 001</span>
<span class="token keyword">var</span> <span class="token function-variable function">removeElements</span> <span class="token operator">=</span> <span class="token keyword">function</span><span class="token punctuation">(</span><span class="token parameter">head<span class="token punctuation">,</span> val</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
  <span class="token comment">// head：6-&gt;7-&gt;8-&gt;null</span>
  <span class="token comment">//步骤1</span>
  <span class="token keyword">if</span> <span class="token punctuation">(</span>head <span class="token operator">==</span> <span class="token keyword">null</span><span class="token punctuation">)</span> <span class="token keyword">return</span> <span class="token keyword">null</span><span class="token punctuation">;</span>

  <span class="token comment">//步骤2</span>
  head<span class="token punctuation">.</span>next <span class="token operator">=</span> <span class="token function">removeElements</span><span class="token punctuation">(</span>head<span class="token punctuation">.</span>next<span class="token punctuation">,</span> val<span class="token punctuation">)</span><span class="token punctuation">;</span>
  <span class="token comment">//步骤3</span>
  <span class="token keyword">return</span> head<span class="token punctuation">.</span>val <span class="token operator">==</span> val <span class="token operator">?</span> head<span class="token punctuation">.</span>next <span class="token operator">:</span> head<span class="token punctuation">;</span>
<span class="token punctuation">}</span><span class="token punctuation">;</span>
<span class="token comment">// 这时候回到操作函数编号 002的上一层中来，</span>
<span class="token comment">// 操作函数编号 001 调用到了步骤2，head.next接收到的返回值为节点 8-&gt;null，</span>
<span class="token comment">// 继续操作函数编号 001 的步骤3，判断当前节点的val是否为7，</span>
<span class="token comment">// 函数编号 001 中当前节点的val为6，所以返回当前的节点 head：6-&gt;8-&gt;null，</span>
<span class="token comment">// 之前当前节点 为head：6-&gt;7-&gt;8-&gt;null，由于head.next在步骤2时发生了改变，</span>
<span class="token comment">// 原来老的head.next（head：7-&gt;8-&gt;null） 从链表中剔除了，</span>
<span class="token comment">// 所以当前节点 为head：6-&gt;8-&gt;null。</span>

<span class="token comment">// 链表中包含节点的val为7的节点都被剔除，操作完毕。</span>
</code></pre></div><h2 id="递归算法的调试"><a href="#递归算法的调试" class="header-anchor">#</a> 递归算法的调试</h2> <p>可以以动画的方式展示递归函数底层的运行机理，一帧一帧的动画来展示递归函数的具体执行过程。</p> <p>但是在实际调试递归函数时</p> <ol><li>很难画出那么详细的动画，相对也比较费时间，</li> <li>但是也可以拿一张 A4 的白纸仔细的一下，</li> <li>例如 画一个比较小的测试用例的执行过程是怎样的，</li> <li>这样对于理解你的程序或者找出你的程序中有错误，</li> <li>是非常有帮助的</li></ol> <p>调试方法靠打印输出，完全可以使用打印输出的方式清楚的看出程序在执行过程中是怎样一步一步获得最终结果。单步跟踪，也就是每一个 IDE 中自带的调试功能。视情况来定。</p> <p>对于递归函数来说有一个非常重要的概念，递归的深度，每一个函数在自己的内部都会去调用了一下自己，那么就代表每次调用自己时，整个递归的深度就多了 1，所以在具体的输出可视化这个递归函数时，这个递归深度是可以帮助你理解这个递归过程的一个变量，在原递归函数中新增一个参数<code>depth</code>，根据这个变量生成递归深度字符串<code>--</code>，<code>--</code>相同则代表同一递归深度。</p> <p>很多时候要想真正理解一个算法或者理解一个函数，其实并没有什么捷径，肯定是要费一些劲，如果你不想在纸上画出来的话，那么你就要用代码画出来，也就是要在代码上添加很多的辅助代码，这就是平时去理解程序或做练习时不要去犯懒，可能只要写 4 行代码就能解决问题，但是这背后很有可能是你写了几十行甚至上百行的代码最终终于透彻的理解了这个程序，然后才能潇洒的用四行代码来解决这个问题。</p> <p>不停的练习如何写一个递归的函数，才能理解理解这个递归的过程。</p> <h3 id="代码示例"><a href="#代码示例" class="header-anchor">#</a> 代码示例</h3> <p><code>(class: ListNode, class: Solution)</code></p> <p><strong>ListNode</strong></p> <div class="language-js extra-class"><pre class="language-js"><code><span class="token keyword">class</span> <span class="token class-name">ListNode</span> <span class="token punctuation">{</span>
  <span class="token function">constructor</span><span class="token punctuation">(</span><span class="token parameter">val</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
      <span class="token keyword">this</span><span class="token punctuation">.</span>val <span class="token operator">=</span> val<span class="token punctuation">;</span>
      <span class="token keyword">this</span><span class="token punctuation">.</span>next <span class="token operator">=</span> <span class="token keyword">null</span><span class="token punctuation">;</span>
  <span class="token punctuation">}</span>

  <span class="token comment">// 将一个数组对象 转换为一个链表 并且追加到当前节点上</span>
  <span class="token function">appendToLinkedListNode</span><span class="token punctuation">(</span><span class="token parameter">array</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
      <span class="token keyword">let</span> head <span class="token operator">=</span> <span class="token keyword">null</span><span class="token punctuation">;</span>
      <span class="token keyword">if</span> <span class="token punctuation">(</span><span class="token keyword">this</span><span class="token punctuation">.</span>val <span class="token operator">===</span> <span class="token keyword">null</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token comment">// 头部添加</span>
        head <span class="token operator">=</span> <span class="token keyword">this</span><span class="token punctuation">;</span>
        head<span class="token punctuation">.</span>val <span class="token operator">=</span> array<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span><span class="token punctuation">;</span>
        head<span class="token punctuation">.</span>next <span class="token operator">=</span> <span class="token keyword">null</span><span class="token punctuation">;</span>
      <span class="token punctuation">}</span> <span class="token keyword">else</span> <span class="token punctuation">{</span>
        <span class="token comment">// 插入式</span>
        head <span class="token operator">=</span> <span class="token keyword">new</span> <span class="token class-name">ListNode</span><span class="token punctuation">(</span>array<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        head<span class="token punctuation">.</span>next <span class="token operator">=</span> <span class="token keyword">this</span><span class="token punctuation">.</span>next<span class="token punctuation">;</span>
        <span class="token keyword">this</span><span class="token punctuation">.</span>next <span class="token operator">=</span> head<span class="token punctuation">;</span>
      <span class="token punctuation">}</span>

      <span class="token comment">// 添加节点的方式  头部添加、尾部添加、中间插入</span>

      <span class="token comment">// 尾部添加节点的方式</span>
      <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">var</span> i <span class="token operator">=</span> <span class="token number">1</span><span class="token punctuation">;</span> i <span class="token operator">&lt;</span> array<span class="token punctuation">.</span>length<span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        head<span class="token punctuation">.</span>next <span class="token operator">=</span> <span class="token keyword">new</span> <span class="token class-name">ListNode</span><span class="token punctuation">(</span>array<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        head <span class="token operator">=</span> head<span class="token punctuation">.</span>next<span class="token punctuation">;</span>
      <span class="token punctuation">}</span>
  <span class="token punctuation">}</span>

  <span class="token comment">// 输出链表中的信息</span>
  <span class="token comment">// @Override toString 2018-10-21-jwl</span>
  <span class="token comment">// toString () {</span>
  <span class="token comment">//   let arrInfo = `ListNode: \n`;</span>
  <span class="token comment">//   arrInfo += `data = front  [`;</span>
  <span class="token comment">//   let node = this;</span>
  <span class="token comment">//   while (node.next !== null) {</span>
  <span class="token comment">//     arrInfo += `${node.val}-&gt;`;</span>
  <span class="token comment">//     node = node.next;</span>
  <span class="token comment">//   }</span>
  <span class="token comment">//   arrInfo += `${node.val}-&gt;`;</span>
  <span class="token comment">//   arrInfo += &quot;NULL] tail&quot;;</span>

  <span class="token comment">//   // 在页面上展示</span>
  <span class="token comment">//   document.body.innerHTML += `${arrInfo}&lt;br /&gt;&lt;br /&gt; `;</span>

  <span class="token comment">//   return arrInfo;</span>
  <span class="token comment">// }</span>

  <span class="token function">toString</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
      <span class="token keyword">let</span> arrInfo <span class="token operator">=</span> <span class="token template-string"><span class="token template-punctuation string">`</span><span class="token string">ListNode = </span><span class="token template-punctuation string">`</span></span><span class="token punctuation">;</span>
      arrInfo <span class="token operator">+=</span> <span class="token template-string"><span class="token template-punctuation string">`</span><span class="token string">front  [</span><span class="token template-punctuation string">`</span></span><span class="token punctuation">;</span>
      <span class="token keyword">let</span> node <span class="token operator">=</span> <span class="token keyword">this</span><span class="token punctuation">;</span>
      <span class="token keyword">while</span> <span class="token punctuation">(</span>node<span class="token punctuation">.</span>next <span class="token operator">!==</span> <span class="token keyword">null</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        arrInfo <span class="token operator">+=</span> <span class="token template-string"><span class="token template-punctuation string">`</span><span class="token interpolation"><span class="token interpolation-punctuation punctuation">${</span>node<span class="token punctuation">.</span>val<span class="token interpolation-punctuation punctuation">}</span></span><span class="token string">-&gt;</span><span class="token template-punctuation string">`</span></span><span class="token punctuation">;</span>
        node <span class="token operator">=</span> node<span class="token punctuation">.</span>next<span class="token punctuation">;</span>
      <span class="token punctuation">}</span>
      arrInfo <span class="token operator">+=</span> <span class="token template-string"><span class="token template-punctuation string">`</span><span class="token interpolation"><span class="token interpolation-punctuation punctuation">${</span>node<span class="token punctuation">.</span>val<span class="token interpolation-punctuation punctuation">}</span></span><span class="token string">-&gt;</span><span class="token template-punctuation string">`</span></span><span class="token punctuation">;</span>
      arrInfo <span class="token operator">+=</span> <span class="token string">'NULL] tail'</span><span class="token punctuation">;</span>

      <span class="token keyword">return</span> arrInfo<span class="token punctuation">;</span>
  <span class="token punctuation">}</span>
<span class="token punctuation">}</span>
</code></pre></div><p><strong>Solution</strong></p> <div class="language-js extra-class"><pre class="language-js"><code><span class="token keyword">class</span> <span class="token class-name">Solution</span> <span class="token punctuation">{</span>
  <span class="token comment">// leetcode 203. 移除链表元素</span>
  <span class="token function">removeElements</span><span class="token punctuation">(</span><span class="token parameter">head<span class="token punctuation">,</span> val</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
      <span class="token comment">/**
      * Definition for singly-linked list.
      * function ListNode(val) {
      *     this.val = val;
      *     this.next = null;
      * }
      */</span>
      <span class="token comment">/**
      * @param {ListNode} head
      * @param {number} val
      * @return {ListNode}
      */</span>
      <span class="token comment">// 深入理解递归过程</span>
      <span class="token keyword">var</span> <span class="token function-variable function">removeElements</span> <span class="token operator">=</span> <span class="token keyword">function</span><span class="token punctuation">(</span><span class="token parameter">head<span class="token punctuation">,</span> val<span class="token punctuation">,</span> depth <span class="token operator">=</span> <span class="token number">0</span></span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token comment">// 首次输出 开始调用函数</span>
        <span class="token keyword">let</span> depthString <span class="token operator">=</span> <span class="token function">generateDepathString</span><span class="token punctuation">(</span>depth<span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token keyword">let</span> info <span class="token operator">=</span> depthString <span class="token operator">+</span> <span class="token string">'Call: remove '</span> <span class="token operator">+</span> val <span class="token operator">+</span> <span class="token string">' in '</span> <span class="token operator">+</span> head<span class="token punctuation">;</span>
        <span class="token function">show</span><span class="token punctuation">(</span>info<span class="token punctuation">)</span><span class="token punctuation">;</span>

        <span class="token keyword">if</span> <span class="token punctuation">(</span>head <span class="token operator">===</span> <span class="token keyword">null</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
            <span class="token comment">// 第二次输出  解决最基本的问题时</span>
            info <span class="token operator">=</span> depthString <span class="token operator">+</span> <span class="token string">'Return ：'</span> <span class="token operator">+</span> head<span class="token punctuation">;</span>
            <span class="token function">show</span><span class="token punctuation">(</span>info<span class="token punctuation">)</span><span class="token punctuation">;</span>

            <span class="token keyword">return</span> <span class="token keyword">null</span><span class="token punctuation">;</span>
        <span class="token punctuation">}</span>

        <span class="token keyword">let</span> result <span class="token operator">=</span> <span class="token function">removeElements</span><span class="token punctuation">(</span>head<span class="token punctuation">.</span>next<span class="token punctuation">,</span> val<span class="token punctuation">,</span> depth <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">)</span><span class="token punctuation">;</span>

        <span class="token comment">// 第三次输出 将原问题分解为小问题</span>
        info <span class="token operator">=</span> depthString <span class="token operator">+</span> <span class="token string">'After： remove '</span> <span class="token operator">+</span> val <span class="token operator">+</span> <span class="token string">' ：'</span> <span class="token operator">+</span> result<span class="token punctuation">;</span>
        <span class="token function">show</span><span class="token punctuation">(</span>info<span class="token punctuation">)</span><span class="token punctuation">;</span>

        <span class="token keyword">let</span> ret <span class="token operator">=</span> <span class="token keyword">null</span><span class="token punctuation">;</span>
        <span class="token keyword">if</span> <span class="token punctuation">(</span>head<span class="token punctuation">.</span>val <span class="token operator">===</span> val<span class="token punctuation">)</span> <span class="token punctuation">{</span>
            ret <span class="token operator">=</span> result<span class="token punctuation">;</span>
        <span class="token punctuation">}</span> <span class="token keyword">else</span> <span class="token punctuation">{</span>
            head<span class="token punctuation">.</span>next <span class="token operator">=</span> result<span class="token punctuation">;</span>
            ret <span class="token operator">=</span> head<span class="token punctuation">;</span>
        <span class="token punctuation">}</span>

        <span class="token comment">// 第四次输出 求出小问题的解</span>
        info <span class="token operator">=</span> depthString <span class="token operator">+</span> <span class="token string">'Return ：'</span> <span class="token operator">+</span> ret<span class="token punctuation">;</span>
        <span class="token function">show</span><span class="token punctuation">(</span>info<span class="token punctuation">)</span><span class="token punctuation">;</span>

        <span class="token keyword">return</span> ret<span class="token punctuation">;</span>
      <span class="token punctuation">}</span><span class="token punctuation">;</span>

      <span class="token comment">// 辅助函数 生成递归深度字符串</span>
      <span class="token keyword">function</span> <span class="token function">generateDepathString</span><span class="token punctuation">(</span><span class="token parameter">depth</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token keyword">let</span> arrInfo <span class="token operator">=</span> <span class="token template-string"><span class="token template-punctuation string">`</span><span class="token template-punctuation string">`</span></span><span class="token punctuation">;</span>
        <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">var</span> i <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> i <span class="token operator">&lt;</span> depth<span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
            arrInfo <span class="token operator">+=</span> <span class="token template-string"><span class="token template-punctuation string">`</span><span class="token string">-- </span><span class="token template-punctuation string">`</span></span><span class="token punctuation">;</span> <span class="token comment">// -- 表示深度，--相同则代表在同一递归深度</span>
        <span class="token punctuation">}</span>
        <span class="token keyword">return</span> arrInfo<span class="token punctuation">;</span>
      <span class="token punctuation">}</span>

      <span class="token comment">// 辅助函数 输出内容 到页面和控制台上</span>
      <span class="token keyword">function</span> <span class="token function">show</span><span class="token punctuation">(</span><span class="token parameter">content</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        document<span class="token punctuation">.</span>body<span class="token punctuation">.</span>innerHTML <span class="token operator">+=</span> <span class="token template-string"><span class="token template-punctuation string">`</span><span class="token interpolation"><span class="token interpolation-punctuation punctuation">${</span>content<span class="token interpolation-punctuation punctuation">}</span></span><span class="token string">&lt;br /&gt;&lt;br /&gt;</span><span class="token template-punctuation string">`</span></span><span class="token punctuation">;</span>
        console<span class="token punctuation">.</span><span class="token function">log</span><span class="token punctuation">(</span>content<span class="token punctuation">)</span><span class="token punctuation">;</span>
      <span class="token punctuation">}</span>

      <span class="token keyword">return</span> <span class="token function">removeElements</span><span class="token punctuation">(</span>head<span class="token punctuation">,</span> val<span class="token punctuation">)</span><span class="token punctuation">;</span>
  <span class="token punctuation">}</span>
<span class="token punctuation">}</span>
<span class="token keyword">class</span> <span class="token class-name">Main</span> <span class="token punctuation">{</span>
  <span class="token function">constructor</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
      <span class="token keyword">this</span><span class="token punctuation">.</span><span class="token function">alterLine</span><span class="token punctuation">(</span><span class="token string">'leetcode 203. 删除指定元素的所有节点(递归) 调试'</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
      <span class="token keyword">let</span> s <span class="token operator">=</span> <span class="token keyword">new</span> <span class="token class-name">Solution</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>

      <span class="token keyword">let</span> arr <span class="token operator">=</span> <span class="token punctuation">[</span><span class="token number">1</span><span class="token punctuation">,</span> <span class="token number">2</span><span class="token punctuation">,</span> <span class="token number">3</span><span class="token punctuation">]</span><span class="token punctuation">;</span>
      <span class="token keyword">let</span> node <span class="token operator">=</span> <span class="token keyword">new</span> <span class="token class-name">ListNode</span><span class="token punctuation">(</span><span class="token keyword">null</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
      node<span class="token punctuation">.</span><span class="token function">appendToLinkedListNode</span><span class="token punctuation">(</span>arr<span class="token punctuation">)</span><span class="token punctuation">;</span>
      <span class="token keyword">this</span><span class="token punctuation">.</span><span class="token function">show</span><span class="token punctuation">(</span>node<span class="token punctuation">)</span><span class="token punctuation">;</span>
      s<span class="token punctuation">.</span><span class="token function">removeElements</span><span class="token punctuation">(</span>node<span class="token punctuation">,</span> <span class="token number">2</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
  <span class="token punctuation">}</span>

  <span class="token comment">// 将内容显示在页面上</span>
  <span class="token function">show</span><span class="token punctuation">(</span><span class="token parameter">content</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
      document<span class="token punctuation">.</span>body<span class="token punctuation">.</span>innerHTML <span class="token operator">+=</span> <span class="token template-string"><span class="token template-punctuation string">`</span><span class="token interpolation"><span class="token interpolation-punctuation punctuation">${</span>content<span class="token interpolation-punctuation punctuation">}</span></span><span class="token string">&lt;br /&gt;&lt;br /&gt;</span><span class="token template-punctuation string">`</span></span><span class="token punctuation">;</span>
  <span class="token punctuation">}</span>

  <span class="token comment">// 展示分割线</span>
  <span class="token function">alterLine</span><span class="token punctuation">(</span><span class="token parameter">title</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
      <span class="token keyword">let</span> line <span class="token operator">=</span> <span class="token template-string"><span class="token template-punctuation string">`</span><span class="token string">--------------------</span><span class="token interpolation"><span class="token interpolation-punctuation punctuation">${</span>title<span class="token interpolation-punctuation punctuation">}</span></span><span class="token string">----------------------</span><span class="token template-punctuation string">`</span></span><span class="token punctuation">;</span>
      console<span class="token punctuation">.</span><span class="token function">log</span><span class="token punctuation">(</span>line<span class="token punctuation">)</span><span class="token punctuation">;</span>
      document<span class="token punctuation">.</span>body<span class="token punctuation">.</span>innerHTML <span class="token operator">+=</span> <span class="token template-string"><span class="token template-punctuation string">`</span><span class="token interpolation"><span class="token interpolation-punctuation punctuation">${</span>line<span class="token interpolation-punctuation punctuation">}</span></span><span class="token string">&lt;br /&gt;&lt;br /&gt;</span><span class="token template-punctuation string">`</span></span><span class="token punctuation">;</span>
  <span class="token punctuation">}</span>
<span class="token punctuation">}</span>
</code></pre></div><h2 id="总结"><a href="#总结" class="header-anchor">#</a> 总结</h2> <p>关于递归，链表有天然递归性质结构，几乎和链表相关的所有操作，都可以使用递归的形式完成。</p> <p>练习时可以对链表的增删改查进行递归实现，之前链表的增删改查使用了循环的方式进行了实现，现在可以对链表的增删改成进行递归的方式实现，这个练习是非常有意义的，能够帮助你更好的理解递归。虽然实际使用链表时是不需要使用递归的，但是进行一下这种练习可以让你更好的对递归有更深刻的理解。</p> <p>其它和链表相关的题目 leetcode 上有，链表：<code>https://leetcode-cn.com/tag/linked-list/</code>。<br>
不要完美主义，不要想着把这些问题一下子全部做出来，根据自己的实际情况来制定计划，在自己处于什么样的水平的时候，完成怎样的问题，但是这些问题一直都会在 leetcode 上，慢慢来，一点一点的实现。</p> <p>关于链表的技术研究，由斯坦福提出的问题研究，文章地址：<code>https://max.book118.com/html/2017/0902/131359982.shtm</code>，都看懂了，那你就完全的懂了链表。</p> <p>非线性数据结构，如大名鼎鼎的二分搜索树二分搜索树也是一个动态的数据结构也是靠节点挂接起来的，只不过那些节点没有排成一根线，而是排成了一颗树，不是每一个节点有指向下一个节点的 next，而是由指向左子树和右子树的两个根节点而已。</p> <h2 id="扩展"><a href="#扩展" class="header-anchor">#</a> 扩展</h2> <h3 id="双链表"><a href="#双链表" class="header-anchor">#</a> 双链表</h3> <p>对于队列来说需要对链表的两端进行操作，在两端进行操作的时候就遇到了问题，在尾端删除元素，即使在尾端有 tail 的变量指向链表的结尾，它依然是一个<code>O(n)</code>复杂度的。
对于这个问题其实有一个解决方案，这个问题的解决方案就是双链表，所谓的双链表就是在链表中每一个节点包含两个指针指针就代表着引用，有一个变量 next 指向这个节点的下一个节点，有一个变量 prev 指向这个节点的前一个节点，对于双链表来说，你有了 tail 这个节点之后，删除尾部的节点就非常简单，而且这个操作会是<code>O(1)</code>级别的，但是代价是每一个节点从原来只有一个指针变为两个指针，那么维护起来就会相对复杂一些。</p> <div class="language-js extra-class"><pre class="language-js"><code><span class="token keyword">class</span> <span class="token class-name">Node</span> <span class="token punctuation">{</span>
  e<span class="token punctuation">;</span> <span class="token comment">// Element</span>
  next<span class="token punctuation">;</span> <span class="token comment">//Node</span>
  prev<span class="token punctuation">;</span> <span class="token comment">//Node</span>
<span class="token punctuation">}</span>
</code></pre></div><h3 id="循环链表"><a href="#循环链表" class="header-anchor">#</a> 循环链表</h3> <p>对于循环链表来说，也可以使用双链表的思路来实现，不过需要设立一个虚拟的头节点，从而让整个链表形成了一个环，这里面最重要的是 尾节点不指向空而是指向虚拟头节点，可以很方便的判断某一个节点的下一个节点是否是虚拟头节点，来确定这个节点是不是尾节点。<br>
循环链表的好处是 进一步的把很多操作进行了统一。比如说在链表结尾添加元素只需要在 dummyHead 的前面添加要一个给元素，它就等于是在整个链表的结尾添加了一个元素，事实上循环链表本身是非常有用的，是强类型语言 Java 中的 LinkedList 类底层的实现，本质就是一个循环链表，更准确一些，就是循环双向链表，因为每个节点是有两个指针的。</p> <h3 id="链表也是使用数组来实现"><a href="#链表也是使用数组来实现" class="header-anchor">#</a> 链表也是使用数组来实现</h3> <p>因为链表的 next 只是指向下一个元素，在数组中每一个位置存储的不仅仅是有这个元素，再多存储一个指向下一个元素的索引。<br>
这个链表中每一个节点是这样的，Node 类中有一个 int 的变量 next 指向下一个元素的索引。在有一些情况下，比如你明确的知道你要处理的元素有多少个，这种时候使用这种数组链表有可能是更加方便的。</p> <div class="language-js extra-class"><pre class="language-js"><code><span class="token keyword">class</span> <span class="token class-name">Node</span> <span class="token punctuation">{</span>
   e<span class="token punctuation">;</span> <span class="token comment">// Element</span>
   next<span class="token punctuation">;</span> <span class="token comment">//int</span>
<span class="token punctuation">}</span>
</code></pre></div></div></div> <div class="page-edit"><!----> <div class="tags"><a href="/tags/?tag=%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84" title="标签">#数据结构</a></div> <div class="last-updated"><span class="prefix">上次更新时间:</span> <span class="time">10年18月2023日 01时57分53秒</span></div></div> <div class="page-nav-wapper"><div class="page-nav-centre-wrap"><a href="/pages/24249530353/" class="page-nav-centre page-nav-centre-prev"><div class="tooltip">封装自己的专属链表</div></a> <a href="/pages/7445103033/" class="page-nav-centre page-nav-centre-next"><div class="tooltip">封装自己的专属二分搜索树篇上</div></a></div> <div class="page-nav"><p class="inner"><span class="prev">
        ←
        <a href="/pages/24249530353/" class="prev">封装自己的专属链表</a></span> <span class="next"><a href="/pages/7445103033/"> 封装自己的专属二分搜索树篇上 </a>
        →
      </span></p></div></div></div> <div class="article-list"><div class="article-title"><a href="/archives/" class="iconfont icon-bi">最近更新</a></div> <div class="article-wrapper"><dl><dd>01</dd> <dt><a href="/pages/45343271027/"><div>01.数据结构导论一览.md</div></a> <span>10-16</span></dt></dl><dl><dd>02</dd> <dt><a href="/pages/38850370637/"><div>30.2023年06月04日.md</div></a> <span>06-04</span></dt></dl><dl><dd>03</dd> <dt><a href="/pages/74707370537/"><div>08.与测量相关.md</div></a> <span>05-06</span></dt></dl> <dl><dd></dd> <dt><a href="/archives/" class="more">更多文章&gt;</a></dt></dl></div></div> </main></div> <div class="footer"><!----> 
  Theme by
  <a href="https://github.com/xugaoyi/vuepress-theme-vdoing" target="_blank" title="本站主题">Vdoing</a> 
    | Copyright © 2017-2023
    <span class="link">aiyoudiao 码二</span> <span>备案号：</span> <a href="https://beian.miit.gov.cn/#/Integrated/index" target="_blank" title="备案号">鄂ICP备2022002654号-1</a></div> <div class="buttons"><div title="返回顶部" class="button blur go-to-top iconfont icon-fanhuidingbu" style="display:none;"></div> <div title="去评论" class="button blur go-to-comment iconfont icon-pinglun" style="display:none;"></div></div> <!----> <!----> <!----></div><div class="global-ui"><div></div><APlayer audio="" fixed="true" theme="#b7daff" loop="loop" order="list" preload="auto" volume="0.7" mutex="true" lrc-type="3" list-max-height="250" storage-name="vuepress-plugin-meting" id="aplayer-fixed"></APlayer><div id="VuepressPluginLive2d"></div></div></div>
    <script src="/assets/js/app.bd2fbc77.js" defer></script><script src="/assets/js/3.72c9c947.js" defer></script><script src="/assets/js/138.5bcea4ef.js" defer></script><script src="/assets/js/42.4251ca36.js" defer></script>
  </body>
</html>
